1041:国慶節旅行

#1041:国慶節旅行
時間制限:
1000ms
単一点時限:
1000ms
メモリの制限:
256MB
説明
HiさんとHoさんは国慶節の間にA国へ旅行に行くつもりです.A国の都市間交通は比較的に特色がある:それはnつの都市(番号1-n)を共有している.都市の間にはちょうどn-1本の道路がつながっており、木の道路網を形成している.HiさんはA国の首都(1番都市)を出発して、すべての都市を自転车で遍歴し、道路ごとにちょうど2回--往復各回--このように道路の両側の景色を逃すことはありません.
Hiさんを悩ませたのは、彼の仲間のHoさんが特定の順序でその中のm都市を旅行することを望んでいることだ.例えば3-2-5の順でこの3つの都市を旅行します.(具体的には、初めて3番都市に到着するのは初めて2番都市に到着するより早く、初めて2番都市に到着するのは初めて5番都市に到着するより早い)ことが要求されています.
Hiさんは、Hoさんの要求を満たすドライブ順があるかどうか知りたいと思っています.
入力
入力1行目は、テストデータの数を表す整数T(1<=T<=20)である.
各データの最初の行は、都市数を表す整数n(1<=n<=100)である.
その後、n−1行毎に2つの整数aおよびb(1<=a,b<=n)が、ab間に道路が接続されていることを示す.
次の行には整数m(1<=m<=n)が含まれます.
最後の行にはm個の整数が含まれており,小Hoが望む遊歴順序を表す.
しゅつりょく
YESまたはNOは、Hoの要求を満たすドライブ順序があるかどうかを示す.
サンプル入力

2
7
1 2
1 3
2 4
2 5
3 6
3 7
3
3 7 2
7
1 2
1 3
2 4
2 5
3 6
3 7
3
3 2 7

サンプル出力

YES
NO

この検索問題は帰ってくることができるのは帰って来られないというわけではありません.彼が先に着くことを保証すればいいというわけではありません.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<vector>
#include<bitset>
using namespace std;
#define MAX 111

int m, ok, j, order[MAX], flag[MAX][MAX];
bitset<MAX> digit[MAX];
vector<int> u[MAX];

void canReach(int a, int v)
{
    digit[a][a] = 1;
    for(int i = 0; i < u[a].size(); i++)
    {
        int b = u[a][i];
        if(b == v)
            continue;
        canReach(b, a);
        digit[a] |= digit[b];
    }
}

void dfs(int a, int v)
{
    if(a == order[j])
        j++;
    if(j == m)
    {
        ok = 1;
        return;
    }
    while(j < m)
    {
        int p = j, c = order[j];
        for(int i = 0; i < u[a].size(); i++)
        {
            int b = u[a][i];
            if(b == v)
                continue;
            if(digit[b][c] && flag[a][b])
            {
                flag[a][b] = 0;
                dfs(b, a);
                break;
            }
        }
        if(p == j)
            break;
    }
}

int main(void)
{
    int a, b, i, t, n;
    scanf("%d", &t);
    while(t--)
    {
        ok = j = 0;
        memset(flag, 0, sizeof flag);
        for(i = 0; i < MAX; i++)
        {
            digit[i].reset();
            u[i].clear();
        }
        scanf("%d", &n);
        for(i = 1; i < n; i++)
        {
            scanf("%d%d", &a, &b);
            u[a].push_back(b);
            u[b].push_back(a);
            flag[a][b] = flag[b][a] = 1;
        }
        scanf("%d", &m);
        for(i = 0; i < m; i++)
            scanf("%d", &order[i]);
        canReach(1, -1);
        dfs(1, -1);
        if(ok)
            printf("YES
");
        else
            printf("NO
");
    }
}