#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int V[200005];
int B[200005];
vector<vector<int>> C;
vector<vector<P>> adj;
struct UnionFind {
vector<int> root;
UnionFind(int N) {
root.resize(N);
fill(root.begin(),root.end(),-1);
}
int Find(int n) {
if(root[n]<0) return n;
int r = Find(root[n]);
root[n] = r;
return r;
}
void Merge(int x, int y) {
x = Find(x), y = Find(y);
if(x==y) return;
if(root[x]>root[y]) swap(x, y);
root[x] += root[y];
root[y] = x;
}
};
int Bu = 300;
int par[200005];
array<int, 2> Edge[200005];
bool type[200005]; // Edge type
bool change[200005];
int D[200005];
int id[200005];
int in[200005];
int out[200005];
int global_ETT = 0;
map<int,int> son[200005];
void dfs(int c, int p) {
in[c] = global_ETT;
global_ETT++;
par[c] = p;
int dat = 0;
for(P n2 : adj[c]) {
int n = n2.first;
if(n==p) continue;
dfs(n, c);
son[c][n] = dat;
dat++;
}
C[c].resize(dat);
out[c] = global_ETT;
}
int go_par[200005];
vector<vector<P>> adj2;
int B2[200005];
void dfs2(int c, int p, int pl) {
B2[c] = pl;
for(P k2 : adj2[c]) {
if(k2.first!=p&&type[k2.second]) {
dfs2(k2.first, c, pl);
}
}
}
vector<vector<P>> Query;
int V4[200005];
void dfs3(int c, int p) {
for(P k3 : Query[c]) {
V4[c] += k3.second;
if(par[k3.first] != -1) V4[par[k3.first]] -= k3.second;
}
for(P k2 : adj[c]) {
int n = k2.first;
if(n==p) continue;
dfs3(n, c);
V4[c] += V4[n];
}
}
void dfs4(int c, int p) {
int dat = 0;
for(P k2 : adj[c]) {
int n = k2.first;
if(n==p) continue;
dfs4(n, c);
C[c][dat] = V[n];
dat++;
}
}
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, M, Q;
cin >> N >> M >> Q;
adj.resize(N);
C.resize(N);
int i, j;
for(i=0;i<N-1;i++) {
int a, b;
cin >> a >> b;
adj[a-1].push_back(P(b-1,i));
adj[b-1].push_back(P(a-1,i));
Edge[i] = {a-1, b-1};
}
for(i=0;i<N;i++) V[i] = B[i] = 1;
for(i=0;i<M;i++) {
cin >> D[i];
D[i]--;
}
dfs(0, -1);
for(i=0;i<N;i++) go_par[i] = -1;
for(i=0;i<N-1;i++) {
if(Edge[i][0]!=par[Edge[i][1]]) {
int x = Edge[i][0];
int y = Edge[i][1];
Edge[i] = {y, x};
}
go_par[Edge[i][1]] = i;
}
int pt = 0;
for(i=0;i<M;i++) {
if(i%Bu==Bu-1||i==M-1) {
UnionFind UF(N);
for(j=pt;j<=i;j++) {
change[D[j]] = true;
}
for(j=0;j<N-1;j++) {
if(!change[j]&&type[j]) {
UF.Merge(Edge[j][0], Edge[j][1]);
}
}
for(j=0;j<N;j++) id[j] = UF.Find(j);
vector<vector<int>> V2;
V2.resize(N);
for(j=0;j<N;j++) V2[id[j]].push_back(j);
vector<int> Top;
Top.resize(N);
for(j=0;j<N;j++) {
if(V2[j].size()==0) Top[j] = -1;
else {
int ma1 = -1, mi1 = N+3, id = -1;
for(int n : V2[j]) {
if(out[n] > ma1) {
ma1 = out[n];
mi1 = in[n];
id = n;
}
else if(ma1==out[n]) {
if(in[n] < mi1) {
mi1 = in[n];
id = n;
}
}
}
Top[j] = id;
}
}
for(j=0;j<N;j++) B2[id[j]] = B[j];
adj2.clear();
adj2.resize(N);
vector<int> par2(N);
vector<int> con(N);
for(j=0;j<N;j++) par2[j] = -1;
for(j=0;j<N-1;j++) {
if(change[j]||!type[j]) {
adj2[id[Edge[j][0]]].push_back(P(id[Edge[j][1]], j));
adj2[id[Edge[j][1]]].push_back(P(id[Edge[j][0]], j));
par2[id[Edge[j][1]]] = id[Edge[j][0]];
con[id[Edge[j][1]]] = type[j];
}
}
Query.clear();
Query.resize(N);
vector<int> V3(N);
vector<vector<int>> C3 = C;
for(j=0;j<N;j++) V3[j] = V[j];
for(j=pt;j<=i;j++) {
if(type[D[j]]) {
type[D[j]] = false;
con[id[Edge[D[j]][1]]] = false;
}
else {
int p = Edge[D[j]][0];
int v = Edge[D[j]][1];
int ch = son[p][v];
int pl = V3[v] - C3[p][ch];
int top = id[v];
int dat = Top[id[v]];
assert(dat==v);
while(top != -1) {
if(con[top]) {
int v2 = Top[top];
int p2 = par[v2];
V3[p2] += pl;
C3[v2][son[v2][p2]] = V3[p2];
}
if(!con[top]) break;
top = par2[top];
}
top = Top[top];
//[top, dat) +pl update
Query[p].push_back(P(top, pl));
con[id[v]] = true;
type[D[j]] = true;
dfs2(id[p], -1, B2[id[p]] + pl);
}
}
for(j=0;j<N;j++) V4[j] = 0;
dfs3(0, -1);
for(j=0;j<N;j++) V[j] += V4[j];
dfs4(0, -1);
for(j=0;j<N;j++) B[j] = B2[id[j]];
for(j=pt;j<=i;j++) change[D[j]] = false;
pt = i + 1;
}
}
while(Q--) {
int k;
cin >> k;
cout << B[k-1] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8100 ms |
55900 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8026 ms |
63964 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
9788 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
