树剖入门者求条
查看原帖
树剖入门者求条
322792
Alea楼主2023/11/2 13:40
#include <iostream>
#include <vector>
using namespace std;
const int SIZE=2e5+10;
int n,q;
struct{
    int u,v,w;
}edge[2*SIZE];
vector<int> edgc[SIZE];
int fh[SIZE],siz[SIZE],dep[SIZE],doch[SIZE],fenw[SIZE];
int wson[SIZE],dfn[SIZE],nfd[SIZE],toch[SIZE],dft;
int summ(int x){
    int ans=0;
    for(;x!=0;x-=(x&-x)) ans+=fenw[x];
    return ans;
}
void addd(int x,int v){
    for(;x<=n;x+=(x&-x)) fenw[x]+=v;
}
void dfs(int u,int fa){
    fh[u]=fa,siz[u]=1,dep[u]=dep[fa]+1;
    for(int it:edgc[u]){
        int v=edge[it].v;
        if(v==fa) continue;
        dfs(v,u);
        siz[u]+=siz[v];
        doch[v]=edge[it].w;
        if(siz[wson[u]]<siz[v]) wson[u]=v;
    }
}
void subd(int u,int top){
    toch[u]=top,dfn[u]=++dft,nfd[dft]=u;
    if(wson[u]==0) return;
    subd(wson[u],top);
    for(int it:edgc[u]){
        int v=edge[it].v;
        if(v==fh[u]||v==wson[u]) continue;
        subd(v,v);
    }
}
int qchain(int u,int v){
    int qans=0;
    for(;toch[u]!=toch[v];u=fh[toch[u]]){
        if(dep[toch[u]]<dep[toch[v]]) swap(u,v);
        qans+=summ(dfn[u])-summ(dfn[toch[u]]-1);
    }
    if(u!=v){
        if(dep[u]>dep[v]) swap(u,v);
        qans+=summ(dfn[v])-summ(dfn[u]);
    }
    return qans;
}
int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        if(u<v){
            edge[i]={u,v,w};
            edgc[u].push_back(i);
            edge[i+n-1]={v,u,w};
            edgc[v].push_back(i+n-1);
        }else{
            edge[i]={v,u,w};
            edgc[v].push_back(i);
            edge[i+n-1]={u,v,w};
            edgc[u].push_back(i+n-1);
        }
    }
    dfs(1,1),subd(1,1);
    for(int i=1;i<=n;i++) addd(dfn[i],doch[i]);
    cin>>q;
    while(q--){
        int o,u,v;
        cin>>o>>u>>v;
        if(o==1) addd(dfn[u],v-doch[u]),doch[u]=v;
        else cout<<qchain(u,v)<<endl;
    }
    return 0;
}
2023/11/2 13:40
加载中...