https://www.luogu.com.cn/record/221415788

思路：

3次DFS

• 第一次：找出离节点1最远的白色和黑色节点（记为white、black）

• 第二次：从white出发搜索

• 第三次：从black出发搜索

能否找出我的代码的所有错误点？

如有人调出来，可以得到 $\Large2$ 个关注。谢谢！

#include <iostream>
using namespace std;
const int N=1e5+10;

//邻接表 
struct treenode
{
    int to,nxt;
}g[N];
int pre[N],prel;
void add(int x,int y)
{
    prel++;
    g[prel].to=y;
    g[prel].nxt=pre[x];
    pre[x]=prel;
}

int color[N];//颜色 
int dead[2][N];//标记不能走的同色节点 
int ret;int n;

//DFS 
int dfs(int x,int fa,int c)
{
    int d1=0;//最远的一条路径 
    int d2=0;//次远 
    if(color[x]==c&&((g[pre[x]].nxt==0)||(dead[c][x]==1)))
    {//如果到了思路中所说的节点，那么标记并返回0 
        dead[c][x]=1;
        return 0;
    }
    //搜索 
    for(int i=pre[x];i;i=g[i].nxt)
    {
        int to=g[i].to;
        if(to!=fa)
        {
            int d=dfs(to,x,c)+1;
            if(d>d1)
            {
                d2=d1;
                d1=d;
            }
            else if(d>d2)
            {
                d2=d;
            }
        }
    }
    ret=max(ret,d1+d2);
    return d1;
}

int id,dis;
//找最远节点
void dfs2(int x,int fa,int c,int d)
{
    if(color[x]==c)
    {
        if(d>dis)
        {
            id=x;
            dis=d;
        }
    }
    for(int i=pre[x];i;i=g[i].nxt)
    {
        int to=g[i].to;
        if(to!=fa)
        {
            dfs2(to,x,c,d+1);
        }
    }
    
}

int main()
{
//    freopen("temp.txt","r",stdin);
    //输入、建边 
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>color[i];
    }
    for(int i=1;i<n;i++)
    {
        int x,y;cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    
    int ans=0;
//    //找白色 0
//    for(int i=1;i<=n;i++)
//    {
//        if(color[i]==0)
//        {
//            dfs(i,0,1);
//            ans=max(ret,ans);
//            //break;
//        }
//    }
//    //找黑色 1
//    for(int i=1;i<=n;i++)
//    {
//        if(color[i]==1)
//        {
//            dfs(i,0,0);
//            ans=max(ret,ans);
//            //break;
//        }
//    }
    dfs2(1,0,0,0);
    int black=id;
    id=dis=0; 
    dfs2(1,0,1,0);
    int white=id;
    cout<<black<<' '<<white<<'\n';
    dfs(black,0,0);
    ans=max(ret,ans);
    cout<<ret<<'\n';
    ret=0;
    dfs(white,0,1);
    cout<<ret<<'\n';
    ans=max(ret,ans);
    
    cout<<ans;
    
    return 0;
}