G8008 [GESP202409 八级] 美丽路径 题解

知识点：树的直径、连通分量、建图。

解题思路

只保留两端数值不同的边，原树变成森林；在每个分量中两次BFS求直径，最大边数再加1。

为什么正确

合法路径恰能使用保留边，原树无环保证分量仍是树，最长合法路径就是某分量的直径。

易错点

题目按节点数计长度，所以直径边数要加1；所有边都被删时答案仍为1。

复杂度

时间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;
        if(a[u]!=a[v]) {
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }
    vector<int>vis(n+1),d(n+1,-1);
    auto far=[&](int s,bool mark) {
        vector<int>q= {
            s
        }
        ;
        d[s]=0;
        int last=s;
        for(int k=0;k<(int)q.size();k++) {
            int u=q[k];
            last=u;
            if(mark)vis[u]=1;
            for(int v:g[u])if(d[v]<0) {
                d[v]=d[u]+1;
                q.push_back(v);
            }
        }
        int distance=d[last];
        for(int v:q)d[v]=-1;
        return pair<int,int> {
            last,distance
        }
        ;
    }
    ;
    int ans=1;
    for(int u=1;u<=n;u++)if(!vis[u]) {
        int v=far(u,true).first;
        ans=max(ans,far(v,false).second+1);
    }
    cout<<ans;
}

说明

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