比赛 20120718 评测结果 AAAAAAAATT
题目名称 座位问题 最终得分 80
用户昵称 王者自由 运行时间 0.325 s
代码语言 C++ 内存使用 3.17 MiB
提交时间 2012-07-18 08:56:04
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100000 + 10;
int n, a, b;
bool v[N], h[N];
vector<int> e[N], c[N];
int f[N];
void DFS(int k) {
    v[k] = 1;
    for(int i=0; i<e[k].size(); i++)
        if(!v[e[k][i]]) {
            f[e[k][i]] = k;
            c[k].push_back(e[k][i]);
            DFS(e[k][i]);
        }
}
void Sit(int k) {
    //fprintf(stderr, "%d(%d)->", k, h[k]);
    b += h[k];
    if(k == 1) return;
    Sit(f[k]);
}
int main() {
    freopen("seat.in", "r", stdin);
    freopen("seat.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1; i<n; i++) {
        scanf("%d %d", &a, &b);
        e[a].push_back(b);
        e[b].push_back(a);
    }
    DFS(1);
    /*for(int i=1; i<=n; i++) {
        fprintf(stderr, "\n%d: ", i);
        for(int j=0; j<c[i].size(); j++)
            fprintf(stderr, "%d ", c[i][j]);
    }*/
    for(int i=0; i<n; i++) {
        scanf("%d", &a);
        b = 0;
        Sit(a);
        h[a] = 1;
        printf("%d\n", b);
    }
    return 0;
}