2015
05-24

# How to paint a tree

There is a binary tree, whose vertexes are either black or white, and now YXH wants to paint the tree into only one color. So easy to paint every vertex one by one, so she is not willing to choose this way. She comes up with two ways to paint.
1: Choose two vertexes, then there will be only one shortest path between them, she reverses the color of every vertex on the path (black to white, white to black, including the two vertexes), no two paths can overlap each other;
2: Choose a subtree, reverse the color of all the vertexes on the subtree.

If it costs 1 second to finish any operate, she wants to know at least how long it will take to paint the tree into only one color. (It is obvious that in some situations she has to paint the vertex one by one to minimize the time)

The input contains less than 200 cases, the first line of each case is N (N < 10000), the number of vertexes (1~N). Then n-1 lines, each line has two integers a, b, donating that there is an edge connecting a and b. Then one line has n numbers, 0 or 1, donating the color of the ith vertex;
The tree’s root is always vertex 1.

The input contains less than 200 cases, the first line of each case is N (N < 10000), the number of vertexes (1~N). Then n-1 lines, each line has two integers a, b, donating that there is an edge connecting a and b. Then one line has n numbers, 0 or 1, donating the color of the ith vertex;
The tree’s root is always vertex 1.

6
1 2
1 3
3 4
3 5
5 6
0 0 1 1 1 1
4
1 2
2 3
2 4
1 0 0 0

Case 1: 1
Case 2: 1

Hint
Sample1: you can choose the vertex 2 and 1 to reverse vertex on the path, you also can choose vertex 3 and reverse its sub tree, both of this operate can achieve
the goal in 1 second.
Sample2: you can choose the vertex 4 and vertex 4 to reverse vertex on the path, you also can choose vertex 2 and reverse its sub tree, both of this operate can
achieve the goal in 1 second.


#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <sstream>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
#define CLR(x,k) memset(x,k,sizeof(x))
#define min3(x,y,z) min(min(x,y),z)
#define min4(a,b,c,d) min(min(a,b),min(c,d))
const int MAXN = 10005;

int DP[MAXN][2][2],val[MAXN],vis[MAXN];
void tree_dp(int u)
{
vis[u]=1;
int col=val[u],rec=1-col,dp[3]={},sum=0;
dp[1]=dp[2]=INF;
int v=p->v;
if(vis[v])continue;
tree_dp(v);
sum+=DP[v][col][0];
dp[2]=min(dp[1]+DP[v][rec][1],dp[2]+DP[v][rec][0]);
dp[1]=min(dp[0]+DP[v][rec][1],dp[1]+DP[v][rec][0]);
dp[0]+=DP[v][rec][0];
}
DP[u][col][0]=min4(sum,dp[0]+2,dp[1]+2,dp[2]+2);
DP[u][col][1]=min (dp[0]+1,dp[1]+1);
DP[u][rec][0]=min4(sum+1,dp[0]+1,dp[1]+1,dp[2]+1);
DP[u][rec][1]=min (dp[0],dp[1]);
//    printf("----%d------\n",u);
//    printf("%d\n",DP[u][0][0]);
//    printf("%d\n",DP[u][0][1]);
//    printf("%d\n",DP[u][1][0]);
//    printf("%d\n",DP[u][1][1]);
//    printf("%d %d %d\n",dp[0],dp[1],dp[2]);
}

void init()
{
cur=edges;
CLR(vis,0);
}
int main()
{
///freopen("test.txt","r",stdin);
int N,cas=0;
while(~scanf("%d",&N))
{
init();
for(int i=1,a,b;i<N;++i){
scanf("%d%d",&a,&b);
}
for(int i=1;i<=N;++i)
scanf("%d",val+i);
tree_dp(1);
printf("Case %d: %d\n",++cas,min(DP[1][0][0],DP[1][1][0]));
}
return 0;
}

1. 霍比特人是北美印第安族群！其祖先应是远古亚州人，与中国人是同宗！！！如果其预言有被言中的实际内容，就应该俱可信之处，这个蓝星之兆就等看看有没有可对应的事实吧！但愿大自然慈悲发善，给人类的生存留得有余地、有得退路可行啊、、、、、、

2. 霍比特人是北美印第安族群！其祖先应是远古亚州人，与中国人是同宗！！！如果其预言有被言中的实际内容，就应该俱可信之处，这个蓝星之兆就等看看有没有可对应的事实吧！但愿大自然慈悲发善，给人类的生存留得有余地、有得退路可行啊、、、、、、

3. 霍比特人是北美印第安族群！其祖先应是远古亚州人，与中国人是同宗！！！如果其预言有被言中的实际内容，就应该俱可信之处，这个蓝星之兆就等看看有没有可对应的事实吧！但愿大自然慈悲发善，给人类的生存留得有余地、有得退路可行啊、、、、、、

4. 霍比特人是北美印第安族群！其祖先应是远古亚州人，与中国人是同宗！！！如果其预言有被言中的实际内容，就应该俱可信之处，这个蓝星之兆就等看看有没有可对应的事实吧！但愿大自然慈悲发善，给人类的生存留得有余地、有得退路可行啊、、、、、、

5. 霍比特人是北美印第安族群！其祖先应是远古亚州人，与中国人是同宗！！！如果其预言有被言中的实际内容，就应该俱可信之处，这个蓝星之兆就等看看有没有可对应的事实吧！但愿大自然慈悲发善，给人类的生存留得有余地、有得退路可行啊、、、、、、

6. 霍比特人是北美印第安族群！其祖先应是远古亚州人，与中国人是同宗！！！如果其预言有被言中的实际内容，就应该俱可信之处，这个蓝星之兆就等看看有没有可对应的事实吧！但愿大自然慈悲发善，给人类的生存留得有余地、有得退路可行啊、、、、、、