LCT秒天秒地用什么树剖

这题可以算是树剖的比较裸的题目了

把每一条边的权值下放到他两边的点中深度较深的那个

然后直接用树剖+线段树带进去乱搞就可以了

1 //minamoto  2 #include
     
        3 using namespace std;  4 template
      
       inline bool cmax(T&a,const T&b){
   return a
       
        1<<20)Ot();if(x<0)sr[++C]=45,x=-x; 19     while(z[++Z]=x%10+48,x/=10); 20     while(sr[++C]=z[Z],--Z);sr[++C]='\n'; 21 } 22 const int N=1e5+5; 23 int head[N],Next[N<<1],ver[N<<1],edge[N<<1],tot=1; 24 inline void add(int u,int v,int e){ 25     ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e; 26 } 27 int val[N],num[N],son[N],sz[N],fa[N],dep[N],top[N],dfn[N],cnt; 28 int n; 29 void dfs1(int u){ 30     sz[u]=1,dep[u]=dep[fa[u]]+1; 31     for(int i=head[u];i;i=Next[i]){ 32         int v=ver[i]; 33         if(v!=fa[u]){ 34             fa[v]=u,num[i>>1]=v,dfs1(v),sz[u]+=sz[v]; 35             if(sz[son[u]]
        
         >1; 56     build(ls,l,mid),build(rs,mid+1,r); 57     upd(p); 58 } 59 int query(int p,int l,int r,int ql,int qr){ 60     if(ql<=l&&qr>=r) return mx[p]; 61     int mid=(l+r)>>1,res=0; 62     if(ql<=mid) cmax(res,query(ls,l,mid,ql,qr)); 63     if(qr>mid) cmax(res,query(rs,mid+1,r,ql,qr)); 64     return res; 65 } 66 void update(int p,int l,int r,int x){ 67     if(l==r) return (void)(mx[p]=val[l]); 68     int mid=(l+r)>>1; 69     x<=mid?update(ls,l,mid,x):update(rs,mid+1,r,x); 70     upd(p); 71 } 72 inline void change(int i,int t){ 73     val[dfn[num[i]]]=t,update(1,1,n,dfn[num[i]]); 74 } 75 int query_path(int u,int v){ 76     if(u==v) return 0; 77     int res=0; 78     while(top[u]!=top[v]){ 79         if(dep[top[u]]