首页 > ACM题库 > HDU-杭电 > HDU 4383-How to paint a tree[解题报告]HOJ
2015
05-24

HDU 4383-How to paint a tree[解题报告]HOJ

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;
struct Edge{int v;Edge*next;}edges[MAXN<<1],*cur,*head[MAXN];
inline void add(int u,int v){cur->v=v;cur->next=head[u];head[u]=cur++;}

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;
    for(Edge*p=head[u];p;p=p->next){
        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()
{
    CLR(head,0);
    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);
            add(a,b);add(b,a);
        }
        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;
}