#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x),end(x)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5;
const ll oo = 1e18;
namespace hld {
int n;
int chain[mxN],sz[mxN], parent[mxN],in[mxN], info[mxN], uploaded[mxN] = {};
// vector<edge> edges;
vi adj[mxN];
vector<pi> edges;
set<int,greater<int>> sets[mxN];
int cnt = 0;
void dfs(int at=0, int path=-1) {
int min = in[at] = cnt++;
chain[min] = (path==-1)?min:path;
sets[chain[min]].insert(min);
if(adj[at].empty())
return;
int mx=-2,heavy = -1;
for(int to: adj[at]) {
if(sz[to] > mx) {
mx = sz[to];
heavy=to;
}
}
assert(heavy!=-1);
parent[cnt] = min;
dfs(heavy,chain[min]);
for(int to: adj[at]) {
if(to!=heavy) {
parent[cnt] = min;
dfs(to);
}
}
}
void addedge(int a,int b) {
// edges.push_back({a,b,c});
adj[a].push_back(b);
adj[b].push_back(a);
edges.emplace_back(a,b);
}
void init(int nn) {
n=nn;
fill(sz, sz+n, 1);
fill(parent, parent+n,-1);
fill(info, info+n,1);
vector<pi> q; q.reserve(n); q.emplace_back(0,-1);
// Graph must be a tree
// Do a bfs on nodes
for(int i=0;i<(int)q.size();++i) {
int at,from; tie(at,from) = q[i];
for(int j=0;j<(int)adj[at].size();++j) {
int& to = adj[at][j];
if(to!=from) {
q.emplace_back(to,at);
} else {
swap(to,adj[at].back());
adj[at].pop_back();
j--;
}
}
}
assert(q.size()==n);
for(int i=n-1;i>=0;--i) {
int at = q[i].first;
for(int to: adj[at])
sz[at]+=sz[to];
}
dfs();
}
auto root(int at) { // at = in[node]
while(chain[at]!=0) {
if(!sets[chain[at]].empty() and *sets[chain[at]].rbegin() <= at) {
break;
}
at = parent[chain[at]];
}
return *sets[chain[at]].lower_bound(at);
}
bool update(int i) {
auto [iter,good] = sets[chain[i]].insert(i);
if(!good) {
sets[chain[i]].erase(iter);
}
return good;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m,q; cin >> n >> m >> q;
for(int i=0;i<n-1;++i) {
int a,b; cin >> a >> b;
hld::addedge(a-1,b-1);
}
hld::init(n);
while(m--) {
using namespace hld;
int eid; cin >> eid; eid--;
auto [a,b] = edges[eid];
a = in[a], b = in[b];
if(a>b) swap(a,b);
if(!update(b)) {
info[root(a)]+=info[b]-uploaded[b];
} else {
uploaded[b] = info[b] = info[root(a)];
}
}
while(q--) {
using namespace hld;
int c; cin >> c; c = in[c-1];
cout << info[root(c)] << '\n';
}
return 0;
}
Compilation message
In file included from /usr/include/c++/9/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
from synchronization.cpp:1:
synchronization.cpp: In function 'void hld::init(int)':
synchronization.cpp:69:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
69 | assert(q.size()==n);
| ~~~~~~~~^~~
synchronization.cpp: In function 'bool hld::update(int)':
synchronization.cpp:87:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
87 | auto [iter,good] = sets[chain[i]].insert(i);
| ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:108:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
108 | auto [a,b] = edges[eid];
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
7404 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7404 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7404 KB |
Output is correct |
| 4 |
Correct |
5 ms |
7404 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7404 KB |
Output is correct |
| 6 |
Correct |
7 ms |
7532 KB |
Output is correct |
| 7 |
Correct |
16 ms |
8812 KB |
Output is correct |
| 8 |
Correct |
16 ms |
8812 KB |
Output is correct |
| 9 |
Correct |
16 ms |
8812 KB |
Output is correct |
| 10 |
Correct |
223 ms |
20816 KB |
Output is correct |
| 11 |
Correct |
200 ms |
20816 KB |
Output is correct |
| 12 |
Correct |
266 ms |
27216 KB |
Output is correct |
| 13 |
Correct |
128 ms |
20684 KB |
Output is correct |
| 14 |
Correct |
146 ms |
20320 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
84 ms |
22112 KB |
Output is correct |
| 2 |
Correct |
84 ms |
21860 KB |
Output is correct |
| 3 |
Correct |
91 ms |
25056 KB |
Output is correct |
| 4 |
Correct |
93 ms |
25056 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
7404 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7404 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7404 KB |
Output is correct |
| 4 |
Correct |
5 ms |
7404 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7404 KB |
Output is correct |
| 6 |
Correct |
8 ms |
7532 KB |
Output is correct |
| 7 |
Correct |
22 ms |
9196 KB |
Output is correct |
| 8 |
Correct |
290 ms |
25056 KB |
Output is correct |
| 9 |
Correct |
282 ms |
25056 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
302 ms |
25056 KB |
Output is correct |
| 2 |
Correct |
108 ms |
24928 KB |
Output is correct |
| 3 |
Correct |
110 ms |
25056 KB |
Output is correct |
| 4 |
Correct |
110 ms |
25056 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
7404 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7404 KB |
Output is correct |
| 3 |
Correct |
7 ms |
7404 KB |
Output is correct |
| 4 |
Correct |
7 ms |
7404 KB |
Output is correct |
| 5 |
Correct |
7 ms |
7532 KB |
Output is correct |
| 6 |
Correct |
20 ms |
8860 KB |
Output is correct |
| 7 |
Correct |
290 ms |
21584 KB |
Output is correct |
| 8 |
Correct |
288 ms |
27796 KB |
Output is correct |
| 9 |
Correct |
156 ms |
21836 KB |
Output is correct |
| 10 |
Correct |
178 ms |
21072 KB |
Output is correct |
| 11 |
Correct |
107 ms |
24656 KB |
Output is correct |
| 12 |
Correct |
109 ms |
24656 KB |
Output is correct |
| 13 |
Correct |
112 ms |
27344 KB |
Output is correct |
