题解：P10725 [GESP202406 八级] 最远点对

nb_jzy · 2024-07-09 15:59:30 · 题解

题意

给你一棵树，每个节点有两个颜色，让你求起点和终点为不同颜色的最长路径是多少。

做法

首先，如果没有颜色限制，那么就是求直径。

加上颜色后，因为只有两种颜色，所以我们可以采用求直径的方法，分别维护出每个点到自己子树内的最远的黑点和白点的距离。然后再考虑拼接两条链就行了。

时间复杂度就跟求直径一样，是线性 \mathcal{O}(n) 的。

还有一些小细节，比如当前子树内只有一种颜色的时候，另一种颜色的距离不能赋值为0，不然每次都会加一，会有问题。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int ans,bl[maxn],wh[maxn],a[maxn],n;
vector<int> g[maxn];
void dfs(int u,int fa){
    int maxx1=-1,maxx2=-1;
    for(auto v:g[u]){
        if(v!=fa){
            dfs(v,u);
            if(maxx1!=-1&&wh[v]!=-1){
                ans=max(ans,maxx1+wh[v]+2); 
            }
            if(maxx2!=-1&&bl[v]!=-1){
                ans=max(ans,maxx2+bl[v]+2);
            }//考虑拼接
            maxx1=max(maxx1,bl[v]);
            maxx2=max(maxx2,wh[v]);
            if(bl[v]!=-1){
                bl[u]=max(bl[u],bl[v]+1);
            }
            if(wh[v]!=-1){
                wh[u]=max(wh[u],wh[v]+1);
            }
        }
    }
    if(a[u]==0){
        wh[u]=max(wh[u],0);
        ans=max(ans,maxx1+1);
    }
    else{
        bl[u]=max(bl[u],0);
        ans=max(ans,maxx2+1);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];bl[i]=wh[i]=-1;//赋初值
    }
    int u,v;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    dfs(1,0);
    cout<<ans<<'\n';
    return 0;
}