codeforces 734E（DFS,树的直径（最长路））

题目链接：http://codeforces.com/contest/734/problem/E

题意：有一棵黑白树，每次操作可以使一个同色连通块变色，问最少几次操作能使树变成全黑或全白。

思路：先进行缩点，同色连通块当作一点，用dfs实现并得到新图。答案即为(最长直径+1)/2。

关于最长直径的求法：http://www.cnblogs.com/wuyiqi/archive/2012/04/08/2437424.html

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int col[N],refl[N],maxdis,maxpos;
vector <int> G[N],E[N];
bool vis[N];
void dfs(int x,int cur)
{
    if(vis[x])
        return;
    vis[x] = 1;
    if(col[x] != col[cur])
    {
        E[x].push_back(cur);
        E[cur].push_back(x);
        cur = x;
    }
    for(int i = 0; i < G[x].size(); i++)
        dfs(G[x][i],cur);
}
void DFS(int x,int dis)
{
    if(vis[x])
        return;
    vis[x] = 1;
    if(dis > maxdis)
    {
        maxdis = dis;
        maxpos = x;
    }
    for(int i = 0; i < E[x].size(); i++)
        DFS(E[x][i],dis + 1);
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
        scanf("%d",col + i);
    for(int i = 1; i <= n - 1; i++)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,1);
    memset(vis,0,sizeof(vis));
    DFS(1,0);
    memset(vis,0,sizeof(vis));
    DFS(maxpos,0);
    printf("%d\n",(maxdis + 1) >> 1);
    return 0;
}