Query on a tree

  1 #include<iostream>  2 #include<stdio.h>  3 #include<cstdlib>  4 #include<cstring>  5 using namespace std;  6 const int maxn = 1e4+13;  7   8 struct node  9 { 10     int l,r,Max; 11 }f[maxn*4]; 12  13 struct Edge 14 { 15     int to,next; 16 }edge[maxn*2]; 17  18 int e[maxn][3]; 19 int p[maxn]; 20 int top[maxn]; 21 int siz[maxn]; 22 int son[maxn]; 23 int deep[maxn]; 24 int father[maxn]; 25 int head[maxn]; 26 int num[maxn]; 27 int cont,pos; 28  29 void init() 30 { 31     cont = 0; 32     pos = 0; 33     memset(head,-1,sizeof(head)); 34     memset(son,-1,sizeof(son)); 35 } 36 void add(int n1,int n2) 37 { 38     edge[cont].to=n2;// 指向谁 39     edge[cont].next=head[n1]; 40     head[n1]=cont; 41     cont++; 42 } 43  44 void dfs1(int u,int pre,int d)/**fa deep,num,son**/ 45 { 46     deep[u]=d; 47     father[u]=pre; 48     num[u]=1; 49     for(int i=head[u];i!=-1;i=edge[i].next) 50     { 51         int v = edge[i].to; 52         if(v!=pre) 53         { 54             dfs1(v,u,d+1); 55             num[u]=num[u]+num[v]; 56             if(son[u]==-1 || num[v]>num[son[u]]) 57             son[u]=v; 58         } 59     } 60 } 61  62 void getops(int u,int sp) 63 { 64     top[u]=sp; 65     if(son[u]!=-1) 66     { 67         p[u]=++pos; 68         getops(son[u],sp); 69     } 70     else 71     { 72         p[u]=++pos; 73         return; 74     } 75     for(int i=head[u];i!=-1;i=edge[i].next) 76     { 77         int v = edge[i].to; 78         if(v!=son[u] && v!=father[u]) 79         getops(v,v); 80     } 81 } 82 void build(int l,int r,int n) 83 { 84     f[n].l=l; 85     f[n].r=r; 86     f[n].Max=0; 87     if(l==r)return; 88     int mid=(l+r)/2; 89     build(l,mid,n*2); 90     build(mid+1,r,n*2+1); 91 } 92 int query(int l,int r,int n) 93 { 94     int mid=(f[n].l+f[n].r)/2; 95     int ans1,ans2; 96     if(f[n].l==l && f[n].r==r) return f[n].Max; 97     if(mid>=r) return query(l,r,n*2); 98     else if(mid<l) return query(l,r,n*2+1); 99     else100     {101         ans1=query(l,mid,n*2);102         ans2=query(mid+1,r,n*2+1);103         if(ans1<ans2) ans1=ans2;104     }105     return ans1;106 }107 void update(int x,int num1,int n)108 {109     int mid=(f[n].l+f[n].r)/2;110     if(f[n].l == x && f[n].r == x)111     {112         f[n].Max=num1;113         return;114     }115     if(mid>=x) update(x,num1,n*2);116     else update(x,num1,n*2+1);117     f[n].Max = f[n*2].Max>f[n*2+1].Max? f[n*2].Max:f[n*2+1].Max;118 }119 int find(int u,int v)120 {121     int f1 = top[u],f2 = top[v];122     int MAX=0;123     while(f1!=f2)124     {125        if(deep[f1]<deep[f2])126        {127            swap(f1,f2);128            swap(u,v);129        }130        MAX=max(MAX,query(p[f1],p[u],1));131        u=father[f1];132        f1=top[u];133     }134     if(u==v)return MAX;135     if(deep[u]>deep[v])swap(u,v);136     return max(MAX,query(p[son[u]],p[v],1));137 }138 int main()139 {140     int T,n,l,r,x,num1;141     char a[12];142     scanf("%d",&T);143     while(T--)144     {145         scanf("%d",&n);146         init();147         for(int i=1;i<n;i++)148         {149             scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]);150             add(e[i][0],e[i][1]);151             add(e[i][1],e[i][0]);152         }153         dfs1(1,0,0);154         getops(1,1);155         build(1,pos,1);156         for(int i=1;i<n;i++)157         {158             if(deep[e[i][0]]>deep[e[i][1]]) swap(e[i][0],e[i][1]);159             update(p[e[i][1]],e[i][2],1);160         }161         while(scanf("%s",a)>0)162         {163             if(a[0]==‘D‘)break;164             if(a[0]==‘Q‘)165             {166                 scanf("%d%d",&l,&r);167                 printf("%d\n",find(l,r));168             }169             else if(a[0]==‘C‘)170             {171                 scanf("%d%d",&x,&num1);172                 update(p[e[x][1]],num1,1);173             }174         }175     }176     return 0;177 }