G8005 [GESP202406 八级] 最远点对 题解

知识点：树形动态规划、树的直径、颜色状态。

解题思路

后序维护dp[u][0/1]，表示u到其子树中相应颜色节点的最大距离。合并孩子前，先用当前已合并部分与孩子的相反颜色距离拼出候选路径，再更新两色最长距离。

为什么正确

任意两端不同色的路径在其LCA处由两个分支或根自身拼接；先计算贡献再合并，避免使用同一子树两次。

易错点

不存在某种颜色时该状态应为负无穷；答案按边数计算，初始化当前点颜色距离为0。

复杂度

时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<vector<int>>g(n+1);
    for(int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int>p(n+1),q= {
        1
    }
    ;
    for(int k=0;k<(int)q.size();k++)for(int v:g[q[k]])if(v!=p[q[k]]) {
        p[v]=q[k];
        q.push_back(v);
    }
    vector<array<int,2>>dp(n+1);
    for(auto &x:dp)x.fill(-1000000);
    int ans=0;
    for(int k=n-1;k>=0;k--) {
        int u=q[k];
        dp[u][a[u]]=0;
        for(int v:g[u])if(p[v]==u) {
            ans=max({ans,dp[u][0]+dp[v][1]+1,dp[u][1]+dp[v][0]+1});
            for(int c=0;c<2;c++)dp[u][c]=max(dp[u][c],dp[v][c]+1);
        }
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用16个自行生成的测试点。