比赛 |
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;
}