#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define ld long double
#define vi vector<int>
#define vii vector<vector<int>>
#define all(v) (v).begin(), (v).end()
#define rep(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define per(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
using namespace std;
const int MOD = 1e9 + 7;
int add(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
return a;
}
int mul(int a, int b) {
(a *= b) %= MOD;
return a;
}
int ceil(int x, int y) {
return (x + y - 1) / y;
}
int bin_pow(int x, int y) {
int res = 1;
while (y) {
if (y & 1) res = res * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return res;
}
template<class T> bool minimize(T& a, T b) {
if (a > b) return a = b, true;
return false;
}
template<class T> bool maximize(T& a, T b) {
if (a < b) return a = b, true;
return false;
}
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 1e17;
const int maxn = 2e5 + 5;
const int BASE = 1e6;
const int LG = 17;
int n, m, q, timeDfs;
int fen[maxn + 5];
int tin[maxn + 5], tout[maxn + 5];
int up[maxn + 5][LG + 5];
int h[maxn + 5], res[maxn + 5], data_save[maxn + 5];
vector<int> g[maxn + 5];
vector<pair<int, int>> edge(maxn + 5);
void dfs(int u, int p) {
tin[u] = ++timeDfs;
for (int v : g[u]) {
if (v == p) continue;
up[v][0] = u;
h[v] = h[u] + 1;
dfs(v, u);
}
tout[u] = timeDfs;
}
void upd(int v, int x) {
for (; v <= n; v += v & (-v))
fen[v] += x;
}
int get(int v) {
int ans = 0;
for (; v; v -= v & (-v))
ans += fen[v];
return ans;
}
int go_up(int u) {
for (int j = LG; ~j; --j) {
if ((1ll << j) > h[u]) continue;
int p = up[u][j];
if (h[u] - h[p] == get(tin[u]) - get(tin[p]))
u = up[u][j];
}
return u;
}
void solve(int tc) {
cin >> n >> m >> q;
for (int i = 1; i < n; ++i) {
cin >> edge[i].fi >> edge[i].se;
g[edge[i].fi].push_back(edge[i].se);
g[edge[i].se].push_back(edge[i].fi);
}
dfs(1, 0);
up[1][0] = 1;
for (int j = 1; j <= LG; ++j)
for (int i = 1; i <= n; ++i)
up[i][j] = up[up[i][j - 1]][j - 1];
for (int i = 1; i < n; ++i) {
int u = edge[i].fi;
int v = edge[i].se;
if (h[u] > h[v])
swap(edge[i].fi, edge[i].se);
}
vector<int> status(n + 1, 0);
for (int i = 1; i <= n; ++i) res[i] = 1;
for (int i = 1; i <= m; ++i) {
int d; cin >> d;
int u = edge[d].first, v = edge[d].second;
int par = go_up(u);
status[d] ^= 1;
if (status[d]) {
res[par] += res[v] - data_save[d];
upd(tin[v], 1);
upd(tout[v] + 1, -1);
} else {
res[v] = res[par];
data_save[d] = res[par];
upd(tin[v], -1);
upd(tout[v] + 1, 1);
}
}
for (int i = 1; i <= q; ++i) {
int u; cin >> u;
u = go_up(u);
cout << res[u] << ' ';
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc = 1;
//cin >> tc;
for (int i = 1; i <= tc; ++i) {
solve(i);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
8284 KB |
Output is correct |
2 |
Correct |
3 ms |
8284 KB |
Output is correct |
3 |
Correct |
3 ms |
8284 KB |
Output is correct |
4 |
Correct |
4 ms |
8168 KB |
Output is correct |
5 |
Correct |
3 ms |
8284 KB |
Output is correct |
6 |
Correct |
4 ms |
8540 KB |
Output is correct |
7 |
Correct |
10 ms |
11140 KB |
Output is correct |
8 |
Correct |
13 ms |
11096 KB |
Output is correct |
9 |
Correct |
12 ms |
11100 KB |
Output is correct |
10 |
Correct |
120 ms |
36992 KB |
Output is correct |
11 |
Correct |
142 ms |
36948 KB |
Output is correct |
12 |
Correct |
198 ms |
42576 KB |
Output is correct |
13 |
Correct |
58 ms |
36804 KB |
Output is correct |
14 |
Correct |
105 ms |
35676 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
80 ms |
38984 KB |
Output is correct |
2 |
Correct |
62 ms |
38612 KB |
Output is correct |
3 |
Correct |
115 ms |
41304 KB |
Output is correct |
4 |
Correct |
95 ms |
41304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
8280 KB |
Output is correct |
2 |
Correct |
4 ms |
8284 KB |
Output is correct |
3 |
Correct |
3 ms |
8348 KB |
Output is correct |
4 |
Correct |
4 ms |
8284 KB |
Output is correct |
5 |
Correct |
4 ms |
8308 KB |
Output is correct |
6 |
Correct |
4 ms |
8536 KB |
Output is correct |
7 |
Correct |
21 ms |
11804 KB |
Output is correct |
8 |
Correct |
255 ms |
43376 KB |
Output is correct |
9 |
Correct |
249 ms |
43280 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
254 ms |
43348 KB |
Output is correct |
2 |
Correct |
144 ms |
42320 KB |
Output is correct |
3 |
Correct |
153 ms |
42576 KB |
Output is correct |
4 |
Correct |
141 ms |
42368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
8284 KB |
Output is correct |
2 |
Correct |
3 ms |
8284 KB |
Output is correct |
3 |
Correct |
4 ms |
8284 KB |
Output is correct |
4 |
Correct |
4 ms |
8312 KB |
Output is correct |
5 |
Correct |
4 ms |
8540 KB |
Output is correct |
6 |
Correct |
13 ms |
11140 KB |
Output is correct |
7 |
Correct |
162 ms |
37732 KB |
Output is correct |
8 |
Correct |
241 ms |
43348 KB |
Output is correct |
9 |
Correct |
72 ms |
37884 KB |
Output is correct |
10 |
Correct |
104 ms |
36752 KB |
Output is correct |
11 |
Correct |
86 ms |
40212 KB |
Output is correct |
12 |
Correct |
86 ms |
40144 KB |
Output is correct |
13 |
Correct |
133 ms |
42576 KB |
Output is correct |