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

_zuoqingyuan · 2024-07-09 16:01:14 · 题解

思路分析

对于题目中所描述的最长路径 x\to y，我们将其拆成两部分，分别是 x\to z,z\to y，其中 z 为 x,y 的最近公共祖先。可以枚举 z，找到对应的 x,y。

因为 x,y 的选择互不干扰，我们枚举 z，同时记录 z 的子树中距离节点 z 最远的黑色点/白色点到 z 的距离，然后更新答案即可。具体的，我们设 dp_{u,1/0} 表示 u 的子树中距离 u 最远的黑/白点到 u 的距离，如果 s 为 u 的一个儿子，可以写出转移方程：

更新答案时，为了避免 x,y 位于节点 z 同一儿子的子树中，我们用 dp_{s,1/0} 更新 dp_{u,1/0} 之前，先统计答案。假设路径右端 y 在节点 s 的子树中，路径左端 x 则是在 u 其他子节点的子树中（子节点 s 之前）。则答案 ans 为：

此时就避免了位于同一个子树中的问题。初始时所有 dp_{u,a_u}=0，其余 dp 值均为 -\infty。

树形 dp，时间复杂度 \mathcal{O}(n)。

\text{Code}：

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+10,inf=1e9+10;
int n,to[2*N],nxt[2*N],ver[N],c[N],idx,ans,dp[N][2];
void add(int x,int y){
    to[++idx]=y,nxt[idx]=ver[x],ver[x]=idx;
}
void dfs(int x,int fa){
    dp[x][0]=dp[x][1]=-inf;
    dp[x][c[x]]=0;
    for(int i=ver[x];i;i=nxt[i]){
        if(to[i]==fa)continue;
        int y=to[i];dfs(y,x);
        ans=max(ans,max(dp[x][1]+dp[y][0],dp[x][0]+dp[y][1])+1);
        dp[x][0]=max(dp[x][0],dp[y][0]+1);
        dp[x][1]=max(dp[x][1],dp[y][1]+1);
    }
    return;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",c+i);
    for(int i=1,u,v;i<n;i++){
        scanf("%d %d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}

如有错误，请指出。