【SPOJ-QTREE】树链剖分

树链剖分学习

https://blog.csdn.net/u013368721/article/details/39734871

https://www.cnblogs.com/George1994/p/7821357.html

核心：节点u的轻儿子为v 轻儿子的性质：size[v] <= size[u] / 2

故：每走一条轻链，节点数减少一半

又因：两个节点之间的路径，必为重链和轻边交替

故：从根结点到树上任意点经过的轻边以及重链都不会超过logn条

http://acm.hust.edu.cn/vjudge/problem/13013

树链剖分模版题

题意：

有一棵N个节点的树（1<=N<=10000），N-1条边，边的编号为1~N-1，每条边有一个权值，要求模拟两种操作：

1：QUERY x y 求节点x和节点y之间的路径中权值最大的边。

2：CHANGE p k修改第p条边的权值为k。

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 using namespace std;
  7 
  8 const int N=10010;
  9 char s[10];
 10 struct trnode{
 11     int lc,rc,l,r,c;
 12 }t[2*N];
 13 struct node{
 14     int x,y,d,next;
 15 }a[2*N],b[N];
 16 int n,tl,z,len;
 17 int first[N],tot[N],son[N],fa[N],dep[N],ys[N],top[N];
 18 
 19 int maxx(int x,int y){return x>y ? x:y;}
 20 
 21 void ins(int x,int y,int d)
 22 {
 23     len++;
 24     a[len].x=x;a[len].y=y;a[len].d=d;
 25     a[len].next=first[x];first[x]=len;
 26 }
 27 
 28 int build_tree(int l,int r)
 29 {
 30     int x=++tl;
 31     t[x].l=l;t[x].r=r;t[x].c=0;
 32     t[x].lc=t[x].rc=-1;
 33     if(l<r)
 34     {
 35         int mid=(l+r)>>1;
 36         t[x].lc=build_tree(l,mid);
 37         t[x].rc=build_tree(mid+1,r);
 38     }
 39     return x;
 40 }
 41 
 42 void change(int x,int p,int c)
 43 {
 44     if(t[x].l==t[x].r) {t[x].c=c;return;}
 45     int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)>>1;
 46     if(p<=mid) change(lc,p,c);
 47     else change(rc,p,c);
 48     t[x].c=maxx(t[lc].c,t[rc].c);
 49 }
 50 
 51 int query(int x,int l,int r)
 52 {
 53     if(t[x].l==l && t[x].r==r) return t[x].c;
 54     int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)>>1;
 55     if(r<=mid) return query(lc,l,r);
 56     else if(l>mid) return query(rc,l,r);
 57     return maxx(query(lc,l,mid),query(rc,mid+1,r));
 58 }
 59 
 60 void dfs1(int x)
 61 {
 62     tot[x]=1;son[x]=0;
 63     for(int i=first[x];i;i=a[i].next)
 64     {
 65         int y=a[i].y;
 66         if(y==fa[x]) continue;
 67         fa[y]=x;
 68         dep[y]=dep[x]+1;
 69         dfs1(y);
 70         if(tot[son[x]]<tot[y]) son[x]=y;
 71         tot[x]+=tot[y];
 72     }
 73 }
 74 
 75 void dfs2(int x,int tp)
 76 {
 77     ys[x]=++z;top[x]=tp;
 78     if(son[x]) dfs2(son[x],tp);
 79     for(int i=first[x];i;i=a[i].next)
 80     {
 81         int y=a[i].y;
 82         if(y==fa[x] || y==son[x]) continue;
 83         dfs2(y,y);
 84     }
 85 }
 86 
 87 int solve(int x,int y)
 88 {
 89     int tx=top[x],ty=top[y],ans=0;
 90     while(tx!=ty)
 91     {
 92         if(dep[tx]>dep[ty]) swap(tx,ty),swap(x,y);//debug swap(x,y)之前漏了
 93         ans=maxx(ans,query(1,ys[ty],ys[y]));
 94         y=fa[ty];ty=top[y];
 95     }
 96     if(x==y) return ans;
 97     else 
 98     {
 99         if(dep[x]>dep[y]) swap(x,y);
100         return maxx(ans,query(1,ys[son[x]],ys[y]));
101     }
102 }
103 
104 int main()
105 {
106     freopen("a.in","r",stdin);
107     // freopen("a.out","w",stdout);
108     int T;
109     scanf("%d",&T);
110     while(T--)
111     {
112         scanf("%d",&n);
113         len=0;tl=0;z=0;dep[1]=0;tot[0]=0;
114         memset(fa,0,sizeof(fa));
115         memset(first,0,sizeof(first));
116         for(int i=1;i<n;i++)
117         {
118             scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].d);
119             ins(b[i].x,b[i].y,b[i].d);
120             ins(b[i].y,b[i].x,b[i].d);
121         }
122         dfs1(1);
123         dfs2(1,1);
124         build_tree(1,z);
125         for(int i=1;i<n;i++) if(dep[b[i].x]>dep[b[i].y]) swap(b[i].x,b[i].y);
126         for(int i=1;i<n;i++) change(1,ys[b[i].y],b[i].d);
127         while(1)
128         {
129             scanf("%s",s);
130             int x,y,d;
131             if(s[0]=='Q') 
132             {
133                 scanf("%d%d",&x,&y);
134                 printf("%d
",solve(x,y));
135             }
136             if(s[0]=='C')
137             {
138                 scanf("%d%d",&x,&d);
139                 change(1,ys[b[x].y],d);
140             }
141             if(s[0]=='D') break;
142         }
143     }
144     return 0;
145 }