SPOJ QTREE Query on a tree

Query on a tree

Time Limit: 5000ms

Memory Limit: 262144KB

This problem will be judged on SPOJ. Original ID: QTREE
64-bit integer IO format: %lld Java class name: Main

You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3...N-1.

We will ask you to perfrom some instructions of the following form:

CHANGE i ti : change the cost of the i-th edge to ti
or
QUERY a b : ask for the maximum edge cost on the path from node a to node b

Input

The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.

For each test case:

In the first line there is an integer N (N <= 10000),
In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of cost c (c <= 1000000),
The next lines contain instructions "CHANGE i ti" or "QUERY a b",
The end of each test case is signified by the string "DONE".

There is one blank line between successive tests.

Output

For each "QUERY" operation, write one integer representing its result.

Example

Input:
1

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

Output:
1
3

解题：树链剖分

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 10100;
  4 struct arc{
  5     int to,next;
  6     arc(int x = 0,int y = -1){
  7         to = x;
  8         next = y;
  9     }
 10 }e[30000];
 11 struct node{
 12     int lt,rt,val;
 13 }tree[maxn<<2];
 14 int head[maxn],fa[maxn],dep[maxn],son[maxn],tot;
 15 int siz[maxn],top[maxn],tid[maxn],label;
 16 void add(int u,int v){
 17     e[tot] = arc(v,head[u]);
 18     head[u] = tot++;
 19 }
 20 void Find_heavy_edge(int u,int father,int depth){
 21     siz[u] = 1;
 22     dep[u] = depth;
 23     fa[u] = father;
 24     son[u] = -1;
 25     for(int i = head[u]; ~i; i = e[i].next){
 26         if(e[i].to == father) continue;
 27         Find_heavy_edge(e[i].to,u,depth + 1);
 28         siz[u] += siz[e[i].to];
 29         if(son[u] == -1 || siz[e[i].to] > siz[son[u]])
 30             son[u] = e[i].to;
 31     }
 32 }
 33 void connect_heavy_edge(int u,int ancestor){
 34     tid[u] = label++;
 35     top[u] = ancestor;
 36     if(son[u] != -1) connect_heavy_edge(son[u],ancestor);
 37     for(int i = head[u]; ~i; i = e[i].next){
 38         if(e[i].to == fa[u] || e[i].to == son[u]) continue;
 39         connect_heavy_edge(e[i].to,e[i].to);
 40     }
 41 }
 42 inline void pushup(int v){
 43     tree[v].val = max(tree[v<<1].val,tree[v<<1|1].val);
 44 }
 45 void build(int lt,int rt,int v){
 46     tree[v].lt = lt;
 47     tree[v].rt = rt;
 48     tree[v].val = 0;
 49     if(lt == rt) return;
 50     int mid = (lt + rt)>>1;
 51     build(lt,mid,v<<1);
 52     build(mid+1,rt,v<<1|1);
 53 }
 54 void update(int pos,int val,int v){
 55     if(tree[v].lt == tree[v].rt){
 56         tree[v].val = val;
 57         return;
 58     }
 59     if(pos <= tree[v<<1].rt) update(pos,val,v<<1);
 60     if(pos >= tree[v<<1|1].lt) update(pos,val,v<<1|1);
 61     pushup(v);
 62 }
 63 int query(int lt,int rt,int v){
 64     int ret = 0;
 65     if(lt <= tree[v].lt && rt >= tree[v].rt) return tree[v].val;
 66     if(lt <= tree[v<<1].rt) ret = query(lt,rt,v<<1);
 67     if(rt >= tree[v<<1|1].lt) ret = max(ret,query(lt,rt,v<<1|1));
 68     return ret;
 69 }
 70 int Find(int u,int v){
 71     int f1 = top[u],f2 = top[v],tmp = 0;
 72     while(f1 != f2){
 73         if(dep[f1] < dep[f2]){
 74             swap(f1,f2);
 75             swap(u,v);
 76         }
 77         tmp = max(tmp,query(tid[f1],tid[u],1));
 78         u = fa[f1];
 79         f1 = top[u];
 80     }
 81     if(u == v) return tmp;
 82     if(dep[u] > dep[v]) swap(u,v);
 83     return max(tmp,query(tid[son[u]],tid[v],1));
 84 }
 85 int ac[maxn][3];
 86 int main(){
 87     int kase,n,u,v;
 88     char op[10];
 89     scanf("%d",&kase);
 90     while(kase--){
 91         memset(head,-1,sizeof head);
 92         scanf("%d",&n);
 93         for(int i = tot = 0; i < n-1; ++i){
 94             scanf("%d%d%d",&ac[i][0],&ac[i][1],&ac[i][2]);
 95             add(ac[i][0],ac[i][1]);
 96             add(ac[i][1],ac[i][0]);
 97         }
 98         label = 0;
 99         Find_heavy_edge(1,0,0);
100         connect_heavy_edge(1,1);
101         build(0,label-1,1);
102         for(int i = 0; i < n-1; ++i){
103             if(dep[ac[i][0]] > dep[ac[i][1]])
104                 swap(ac[i][0],ac[i][1]);
105             update(tid[ac[i][1]],ac[i][2],1);
106         }
107         while(~scanf("%s",op)){
108             if(op[0] == 'D') break;
109             scanf("%d%d",&u,&v);
110             if(op[0] == 'Q') printf("%d
",Find(u,v));
111             else update(tid[ac[u-1][1]],v,1);
112         }
113     }
114     return 0;
115 }

View Code

Link-Cut Tree

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 10010;
  4 struct arc{
  5     int to,w,next;
  6     arc(int x = 0,int y = 0,int z = -1){
  7         to = x;
  8         w = y;
  9         next = z;
 10     }
 11 }e[maxn<<1];
 12 int head[maxn],tot;
 13 void add(int u,int v,int w){
 14     e[tot] = arc(v,w,head[u]);
 15     head[u] = tot++;
 16 }
 17 struct LCT{
 18     int fa[maxn],pa[maxn],ch[maxn][2],sz[maxn],maxv[maxn],belong[maxn],key[maxn];
 19     inline void pushup(int x){
 20         maxv[x] = max(max(maxv[ch[x][0]],maxv[ch[x][1]]),key[x]);
 21     }
 22     void rotate(int x,int kd){
 23         int y = fa[x];
 24         ch[y][kd^1] = ch[x][kd];
 25         fa[ch[x][kd]] = y;
 26         fa[x] = fa[y];
 27         fa[y] = x;
 28         ch[x][kd] = y;
 29         if(fa[x]) ch[fa[x]][y == ch[fa[x]][1]] = x;
 30         pushup(y);
 31     }
 32     void splay(int x,int goal = 0){
 33         while(fa[x] != goal){
 34             if(fa[fa[x]] == goal) rotate(x,x == ch[fa[x]][0]);
 35             else{
 36                 int y = fa[x],z = fa[y],s = (y == ch[z][0]);
 37                 if(x == ch[y][s]){
 38                     rotate(x,s^1);
 39                     rotate(x,s);
 40                 }else{
 41                     rotate(y,s);
 42                     rotate(x,s);
 43                 }
 44             }
 45         }
 46         pushup(x);
 47     }
 48     void access(int x){
 49         for(int y = 0; x; x = pa[x]){
 50             splay(x);
 51             fa[ch[x][1]] = 0;
 52             pa[ch[x][1]] = x;
 53             ch[x][1] = y;
 54             fa[y] = x;
 55             pa[y] = 0;
 56             y = x;
 57             pushup(x);
 58         }
 59     }
 60     void build(int _val,int parent,int x){
 61         pa[x] = parent;
 62         maxv[x] = key[x] = _val;
 63         ch[x][0] = ch[x][1] = fa[x] = 0;
 64     }
 65     void change(int ith,int val){
 66         int x = belong[ith-1];
 67         key[x] = val;
 68         splay(x);
 69     }
 70     int query(int x,int y){
 71         access(y);
 72         for(y = 0; x; x = pa[x]){
 73             splay(x);
 74             if(!pa[x]) return max(maxv[y],maxv[ch[x][1]]);
 75             fa[ch[x][1]] = 0;
 76             pa[ch[x][1]] = x;
 77             ch[x][1] = y;
 78             fa[y] = x;
 79             pa[y] = 0;
 80             y = x;
 81             pushup(x);
 82         }
 83         return 0;
 84     }
 85 }lct;
 86 void dfs(int u,int fa){
 87     for(int i = head[u]; ~i; i = e[i].next){
 88         if(e[i].to == fa) continue;
 89         lct.build(e[i].w,u,e[i].to);
 90         lct.belong[i>>1] = e[i].to;
 91         dfs(e[i].to,u);
 92     }
 93 }
 94 int main(){
 95     int kase,n,u,v,w;
 96     char op[10];
 97     scanf("%d",&kase);
 98     while(kase--){
 99         memset(head,-1,sizeof head);
100         tot = 0;
101         scanf("%d",&n);
102         for(int i = 1; i < n; ++i){
103             scanf("%d%d%d",&u,&v,&w);
104             add(u,v,w);
105             add(v,u,w);
106         }
107         dfs(1,1);
108         while(~scanf("%s",op)){
109             if(op[0] == 'D') break;
110             scanf("%d%d",&u,&v);
111             if(op[0] == 'Q') printf("%d
",lct.query(u,v));
112             else if(op[0] == 'C') lct.change(u,v);
113         }
114     }
115     return 0;
116 }

View Code