2015年8月31日 星期一

2015/08/31 HDU 5423 Rikka with Tree

/*
    所求的充要條件是
    同樣的深度d有兩個點
    且 至少有一個點深度為d+1

    如此以來 我們把有兒子
    而深度為d 的點x
    和其他深度同為d的點互換
    即可得到所求
*/
// http://acm.hdu.edu.cn/showproblem.php?pid=5423
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int N;

int d[2000];
vector<int> v[2000];

void DFS(int O, int P, int x)
{
    d[x]++;

    for(int vi = 0; vi < v[O].size(); vi++)
    {
        if( v[O][vi] == P ) continue;
        DFS(v[O][vi], O, x+1);
    }
}

int main()
{
    while( scanf("%d", &N) != EOF )
    {
        for(int Ni = 0; Ni <= N; Ni++) d[Ni] = 0;

        for(int Ni = 1; Ni <= N; Ni++) v[Ni].clear();

        for(int Ni = 1; Ni < N; Ni++)
        {
            int a, b;
            scanf("%d %d", &a, &b);

            v[a].push_back(b);
            v[b].push_back(a);
        }

        DFS(1, 1, 0);

        bool OK = true;

        for(int Ni = 0; Ni < N; Ni++)
            if( d[Ni] > 1 && d[Ni+1] != 0 ) OK = false;

        if( OK ) puts("YES");
        else puts("NO");
    }
}

沒有留言:

張貼留言