题目链接

题意

一颗树，动态修改边权，询问某个点到树上最远点的距离

题解

最远点一定是树的直径的端点之一
所以问题就是动态维护树的直径
考虑用线段树维护dfs序上一段区间说代表的树的直径
合并时，直径有四种可能，分别枚举
用树状数组维护结点到根的距离
修改时，在dfs序上用树状数组修改
查询距离 ( u , v ) (u,v) (u,v)时， d i s ( u ) + d i s ( v ) − 2 ∗ d i s ( L C A ( u , v ) ) dis(u)+dis(v)-2*dis(LCA(u,v)) dis(u)+dis(v)−2∗dis(LCA(u,v))

代码

#include<bits/stdc++.h>
#define N 100010
#define INF 0x3f3f3f3f
#define eps 1e-5
#define pi 3.141592653589793
#define mod 998244353
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x,y) memset(x,0,sizeof(int)*(y+3))
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef pair<int,int> pp;
vector<pp> a[N];
int n,m,fa[N],f[18][N],in[N],out[N],e[N],id[N],L[N],eg[N][2],tot=0;
struct BIT{
    LL d[N];
    inline void up(int x,int y){for(int i=x;i<N;i+=i&-i)d[i]+=y;}
    inline void update(int x,int y,int w) {up(x,w);up(y+1,-w);}
    inline LL sum(int x){LL res=0;for(int i=x;i;i-=i&-i)res+=d[i];return res;}
}BT;

int son[N],top[N],sz[N];
void lable(int x,int ffa){
    sz[x]=1;in[x]=++tot; id[tot]=x;
    for (auto i:a[x])if (i.fi!=ffa){
        L[i.fi]=L[x]+1; fa[i.fi]=x;
        lable(i.fi,x);
        sz[x]+=sz[i.fi];
        if (sz[i.fi]>sz[son[x]]) son[x]=i.fi;
        BT.update(in[i.fi],out[i.fi],e[i.se]);
    }
    out[x]=tot;
}

void dfs(int x,int t){
    top[x]=t; 
    if (!son[x]) return;
    dfs(son[x],t);
    for(auto i:a[x]) if (i.fi!=son[x]&&i.fi!=fa[x]) 
        dfs(i.fi,i.fi);
}

inline int lca(int x,int y){
    while(top[x]!=top[y]){
        if (L[top[x]]<L[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return L[x]<L[y]?x:y;
}
inline LL dis(int u,int v){
    return BT.sum(in[u])+BT.sum(in[v])-2*BT.sum(in[lca(u,v)]);
}

struct node{
    int u,v;LL d;
    friend node operator + (const node a,const node b){
        node c; LL tot;
        c=a.d>b.d?a:b;
        int x=a.u,y=a.v,u=b.u,v=b.v;
        if((tot=dis(x,u))>c.d) c={x,u,tot};
        if((tot=dis(x,v))>c.d) c={x,v,tot};
        if((tot=dis(y,u))>c.d) c={y,u,tot};
        if((tot=dis(y,v))>c.d) c={y,v,tot};
        return c;
    }
}g[N<<2];

void build(int x,int l,int r){
    if (l==r){
        g[x]={id[l],id[l],0};
        return;
    }
    int m=l+r>>1;
    build(x<<1,l,m);
    build(x<<1|1,m+1,r);
    g[x]=g[x<<1]+g[x<<1|1];
}

void update(int x,int l,int r,int fl,int fr){
    if (l==fl&&r==fr) return;
    int m=l+r>>1;
    if (fr<=m) update(x<<1,l,m,fl,fr);else
    if (fl>m) update(x<<1|1,m+1,r,fl,fr);else{
        update(x<<1,l,m,fl,m);
        update(x<<1|1,m+1,r,m+1,fr);
    }
    g[x]=g[x<<1]+g[x<<1|1];
}


int main(int argc, char const *argv[])
{
    sc(n);
    for(int i=1;i<n;i++){
        int x,y;
        sccc(x,y,e[i]);
        eg[i][0]=x; eg[i][1]=y;
        a[x].pb(pp(y,i)); a[y].pb(pp(x,i));
    }
    lable(1,-1);
    dfs(1,1);
    build(1,1,n);
    sc(m);
    while(m--){
        char ch[3]; int x,y;
        scanf("%s",ch); sc(x);
        if (ch[0]=='Q'){
            int u=g[1].u,v=g[1].v;
            printf("%lld\n",max(dis(x,u),dis(x,v)));
        }else{
            sc(y);
            int u=eg[x][0],v=eg[x][1];
            if (fa[u]==v) swap(u,v);
            BT.update(in[v],out[v],y-e[x]);
            e[x]=y;
            update(1,1,n,in[v],out[v]);
        }
    }
    return 0;
}