牛客挑战赛45-D题[坐标]

先将T2的贡献计算出来,然后在T1的对应节点上挂一条边权为dep[i]的边.那么题目就变成了求整棵树的直径.用两遍dfs得出直径的两个端点,然后就得出答案.因为是随机数据,每次暴力更新的点不会很多,暴力更新维护一下端点就行.

下面是官方题解,但是没有代码,加了有注释的代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
const int maxn = 2e5+20;
int n,q,tot;
struct node{
    int v,val;
};
vector<node>e1[maxn],e2[maxn];
int f2[maxn],dep2[maxn];
//dfs1 获取T2的dep2
void dfs1(int u,int fa)
{
    f2[u]=fa;
    for(auto &t:e2[u]){
        if(t.v==fa)continue;
        dep2[t.v]=dep2[u]+t.val;
        dfs1(t.v,u);
    }
}
int f1[maxn],siz[maxn],deep[maxn],son[maxn];
int dep1[maxn];
void dfs2(int u,int fa)
{
    f1[u]=fa;siz[u]=1;deep[u]=deep[fa]+1;
    for(auto &t:e1[u]){
        if(t.v==fa)continue;
        dep1[t.v]=dep1[u]+t.val;
        dfs2(t.v,u);
        siz[u]+=siz[t.v];
        if(!son[u]||siz[t.v]>siz[son[u]])son[u]=t.v;
    }
}
int top[maxn];
void dfs3(int u,int topf)
{
    top[u]=topf;
    if(!son[u])return ;
    dfs3(son[u],topf);
    for(auto &t:e1[u]){
        if(t.v==son[u]||t.v==f1[u])continue;
        dfs3(t.v,t.v);
    }
}
bool vis[maxn];
ll dtree,now,S,E,D;
void dfs4(int u,int dval)
{
    // cout<<u<<' '<<dval;
    vis[u]=true;
    if(dval>dtree)dtree=dval,now=u;
    for(auto &t:e1[u]){
        if(vis[t.v])continue;
        dfs4(t.v,dval+t.val);
    }
}

int lca(int u,int v)
{
    while(top[u]^top[v]){
        if(deep[top[u]]<=deep[top[v]])swap(u,v);
        u=f1[top[u]];
    }
    return deep[u]<deep[v]?u:v;
}

ll dis(int u,int v){
    return dep1[u]+dep1[v]-2*dep1[lca(u,v)];
}
ll w;
void dfs5(int u,int fa)
//暴力询问当更新当前u点时有没有更改原来的S和E
{
    dep1[u+n]+=w;
    ll D1=dis(u+n,S),D2=dis(u+n,E);
    ll D=max(D1,D2);
    if(D1>D2)now=S;else now=E;
    if(D>dtree)dtree=D,S=now,E=n+u;
    for(auto &t:e2[u]){
        if(t.v==fa)continue;
        dfs5(t.v,u);
    }
}

signed main()
{
    cin>>n>>q;
    for(int i=1;i<n;i++){
        int u,v,w;cin>>u>>v>>w;
        // cout<<u<<v<<w<<endl;
        e1[u].push_back({v,w});
        e1[v].push_back({u,w});
    }
    for(int i=1;i<n;i++){
        int u,v,w;cin>>u>>v>>w;
        e2[u].push_back({v,w});
        e2[v].push_back({u,w});
    }
    dfs1(1,0);
    //在得到T2的dep之后给T1加一条边
    for(int i=1;i<=n;i++){
        e1[i].push_back({i+n,dep2[i]});
        e1[i+n].push_back({i,dep2[i]});
    }
    //T1树链剖分
    dfs2(1,0);
    dfs3(1,1);
    //dfs两遍求树的直径
    dfs4(1,0);S=now;
    dtree=0;memset(vis,0,sizeof vis);
    dfs4(S,0);E=now;

    cout<<dtree<<endl;
    for(int i=1;i<=q;i++){
        int u;cin>>u>>w;
        //暴力更新
        dfs5(u,f2[u]);
        cout<<dtree<<endl;
    }
    return 0;
}