POJ 3237树链剖分 - c++编程基础

Tree

Time Limit: 5000MS		Memory Limit: 131072K
Total Submissions: 3189		Accepted: 897

Description

You are given a tree with N nodes. The tree’s nodes are numbered 1 throughN and its edges are numbered 1 through N 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:

`CHANGE` i v	Change the weight of the ith edge to v
`NEGATE` a b	Negate the weight of every edge on the path from a to b
`QUERY` a b	Find the maximum weight of edges on the path from a to b

Input

The input contains multiple test cases. The first line of input contains an integert (t ≤ 20), the number of test cases. Then follow the test cases.

Each test case is preceded by an empty line. The first nonempty line of its containsN (N ≤ 10,000). The next N 1 lines each contains three integersa, b and c, describing an edge connecting nodes a and b with weight c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word “DONE” ends the test case.

Output

For each “QUERY” instruction, output the result on a separate line.

Sample Input

1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Sample Output

1
3

题意：给定一颗树，有三种操作:（1）改变第i条边的权值，（2）将从u到v路径上的权值取反，（3）查询从u到v路径上的最大权。

解题思路：首先轻重链剖分，然后线段树维护最大值，最小值，以及取反标记。

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-1-24 13:55:10
File Name :2.cpp
************************************************ */

#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include 
          
            #include 
           
             #include 
            
              #include 
             
               using namespace std; const int maxn=110000; const int inf=1000000000; int head[maxn],tol,top[maxn],p[maxn],fp[maxn],num[maxn],fa[maxn],son[maxn],deep[maxn],pos; struct node { int next,to; }edge[10*maxn]; void add(int u,int v) { edge[tol].next=head[u]; edge[tol].to=v; head[u]=tol++; } void init() { memset(head,-1,sizeof(head)); tol=0; memset(son,-1,sizeof(son)); pos=0; } void dfs(int u,int pre,int d) { deep[u]=d; num[u]=1; fa[u]=pre; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v==pre)continue; dfs(v,u,d+1); num[u]+=num[v]; if(son[u]==-1||num[v]>num[son[u]]) son[u]=v; } } void getpos(int u,int sp) { top[u]=sp; p[u]=pos++; fp[p[u]]=u; if(son[u]==-1)return; getpos(son[u],sp); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v!=fa[u]&&v!=son[u]) getpos(v,v); } } struct NODE { int l,r,max,min,neg; }tree[6*maxn]; void pushup(int i) { tree[i].max=max(tree[2*i].max,tree[2*i+1].max); tree[i].min=min(tree[2*i].min,tree[2*i+1].min); } void pushdown(int i) { if(tree[i].l==tree[i].r)return; if(tree[i].neg) { tree[2*i].max=-tree[2*i].max; tree[2*i].min=-tree[2*i].min; swap(tree[2*i].max,tree[2*i].min); tree[2*i].neg^=1; tree[2*i+1].max=-tree[2*i+1].max; tree[2*i+1].min=-tree[2*i+1].min; swap(tree[2*i+1].max,tree[2*i+1].min); tree[2*i+1].neg^=1; tree[i].neg=0; } } void build(int l,int r,int i) { tree[i].l=l; tree[i].r=r; tree[i].neg=0; tree[i].max=0; tree[i].min=0; if(l==r)return; int mid=(l+r)/2; build(l,mid,2*i); build(mid+1,r,2*i+1); } void update1(int i,int pos,int val) { if(tree[i].l==tree[i].r) { tree[i].max=tree[i].min=val; tree[i].neg=0; return; } pushdown(i); int

POJ 3237树链剖分(一)