nove.19 Qtree1（还是树剖）

https://www.luogu.com.cn/problem/P4114

注意在跳重链的时候链顶要考虑（即不能dfn[top[u]]+1,dfn[u]）
因为跳完一条重链，u=faz[top[u]]，此后再跳就没有考虑到链顶与链顶faz的边了

然后就是De不出来的bug了
经大佬指点，跳重链的时候比较的不是u和v的深度，而是他们链顶的深度
改好了就过了

ACcode

#include<bits/stdc++.h>
using namespace std;
#define in Read()
typedef long long ll;

ll in{
    ll i=0,f=1; char ch=0;
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') f=-1, ch=getchar();
    while('0'<=ch&&ch<='9') i=(i<<1)+(i<<3)+ch-48, ch=getchar();
    return i*f;
}

const int N=1e5+5;
const int INF=2147483647;
int n,to1[N],to2[N];
ll e_wei[N],wei[N];
vector<int> G[N];
int dep[N],siz[N],faz[N],son[N],top[N],dfn[N],cnt,idx[N];
ll tre[N<<2];

void DFS1(int u,int fa){
    dep[u]=dep[fa]+1;
    siz[u]=1;
    faz[u]=fa;
    for(auto v:G[u]){
        if(v==fa) continue;
        DFS1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v]) son[u]=v;
    }
}

void DFS2(int u,int tp){
    top[u]=tp;
    dfn[u]=++cnt;
    idx[cnt]=u;
    if(!son[u]) return;
    DFS2(son[u],tp);
    for(auto v:G[u]){
        if(v==son[u]||v==faz[u]) continue;
        DFS2(v,v);
    }
}

#define lch p<<1
#define rch p<<1|1

void push_up(int p){ tre[p]=max(tre[lch],tre[rch]);}

void build(int p,int l,int r){
    if(l==r){
        tre[p]=wei[idx[l]];
        return;
    }
    int mid=l+r>>1;
    build(lch,l,mid);
    build(rch,mid+1,r);
    push_up(p);
}

ll query(int p,int l,int r,int L,int R){
    if(L>R) return 0;
    if(L<=l&&r<=R) return tre[p];
    ll res=-INF;
    int mid=l+r>>1;
    if(L<=mid) res=max(res,query(lch,l,mid,L,R));
    if(mid<R) res=max(res,query(rch,mid+1,r,L,R));
    return res;
}

void change(int p,int l,int r,int x,ll t){
    if(l==r){
        tre[p]=t;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) change(lch,l,mid,x,t);
    else change(rch,mid+1,r,x,t);
    push_up(p);
}

#undef lch
#undef rch

ll Query(int u,int v){
    ll ans=-INF;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        ans=max(ans,query(1,1,n,dfn[top[u]],dfn[u]));
        u=faz[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    ans=max(ans,query(1,1,n,dfn[u]+1,dfn[v]));
    return ans;
}

int main(){

    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);

    n=in;
    for(int i=1;i<n;++i){
        int u=in,v=in;
        ll w=in;
        G[u].push_back(v);
        G[v].push_back(u);
        e_wei[i]=w;
        to1[i]=u;
        to2[i]=v;
    }

    DFS1(1,0);
    for(int i=1;i<=n;++i){
        if(dep[to1[i]]<dep[to2[i]]) swap(to1[i],to2[i]);
        wei[to1[i]]=e_wei[i];
    }
    DFS2(1,1);
    build(1,1,n);

    string opt;
    while(true){
        cin>>opt;
        if(opt=="DONE") return 0;
        if(opt=="QUERY"){
            int a=in,b=in;
            if(a==b) printf("0\n");
            else printf("%lld\n",Query(a,b));
        }
        if(opt=="CHANGE"){
            int x=in;
            ll t=in;
            change(1,1,n,dfn[to1[x]],t);
        }
    }
    
}

原文地址：http://www.cnblogs.com/antimony-51/p/16907560.html