自动搬运

查看原文

来自洛谷，原作者为

	_zuoqingyuan 蒟蒻

搬运于2025-08-24 23:00:40，当前版本为作者最后更新于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;
}

如有错误，请指出。