1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 const int maxn = 1e5+7; 7  8 int siz[maxn],dep[maxn],top[maxn],tid[maxn],ran[maxn],fa[maxn],son[maxn]; 9 int tot ,kkk ,head[maxn];10 11 struct node{12     int to,next;13 }EE[maxn*10];14 15 void add_edge(int u,int v){16     EE[kkk].to=v;EE[kkk].next=head[u];head[u]=kkk++;17 }18 19 void init(){20     memset(head,-1,sizeof(head));21     kkk = 0;22     tot = 0;23 }24 25 void dfs1(int x,int u,int d){26     siz[x] = 1;27     son[x] = -1;28     dep[x] = d;29     fa[x] = u;30     for(int i=head[x];i!=-1;i=EE[i].next){31         int to = EE[i].to;32         if(to != fa[x]){33             dfs1(to,x,d+1);34             siz[x] += siz[to];35             if(son[x] == -1 || siz[to] > siz[son[x]])36                 son[x] = to;37         }38     }39 }40 void dfs2(int x,int u){41     top[x] = u;42     tid[x] = ++tot;43     ran[tot] = x;44     if(son[x] != -1) dfs2(son[x],u);45     for(int i=head[x];i!=-1;i=EE[i].next){46         int to = EE[i].to;47         if(to != son[x] && to != fa[x])48             dfs2(to,to);49     }50 }51 52 void update(int x,int y){53     while(top[x] != top[y]){54         if(dep[top[x]] < dep[top[y]]) swap(x,y);55         tre.update(1,tid[top[x]],tid[x]);56         x = fa[top[x]];57     }58     if(dep[x] > dep[y]) swap(x,y);59     if(x != y) tre.update(1,tid[son[x]],tid[y]);//给定边权值60     ///tre.update(1,tid[x],tid[y]); //给节点权值61 }62 63 int query(int x,int y){64     int sum = -1e9-7;65     while(top[x] != top[y]){66         if(dep[top[x]] < dep[top[y]]) swap(x,y);67         sum = max(sum,tre.query(1,tid[top[x]],tid[x]));68         x = fa[top[x]];69     }70     if(dep[x] > dep[y]) swap(x,y);71     if(x != y) sum = max(sum,tre.query(1,tid[son[x]],tid[y]));//给边权值72     ///sum = max(sum,tre.query(1,tid[x],tid[y]));//给节点权值73     return sum;74 }