#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
void setIO(string s) {
ios_base::sync_with_stdio(0); cin.tie(0);
//freopen((s + ".in").c_str(), "r", stdin);
//freopen((s + ".out").c_str(), "w", stdout);
}
int n, m, q;
vector<vector<int>> adj;
vector<pair<int, int>> edges;
vector<int> d;
vector<int> c;
int c1, c2;
void init(string str)
{
setIO(str);
string s;
cin >> n >> m >> q;
adj.resize(n);
for (int i = 1; i < n; i++)
{
cin >> c1 >> c2;
c1--; c2--;
// edge
edges.push_back({ c1, c2 });
// tree
adj[c1].push_back(c2);
adj[c2].push_back(c1);
}
for (int i = 0; i < m ; i++)
{
cin >> c1;
c1--;
d.push_back(c1);
}
for (int i = 0; i < q; i++)
{
cin >> c1;
c1--;
c.push_back(c1);
}
}
vector<int> depth;
vector<int> anc;
vector<int> info;
void dfs(int u, int p, int d)
{
depth[u] = d;
for (auto v : adj[u])
{
if (v == p) continue;
if (depth[v] != -1) continue;
dfs(v, u, d+1);
}
}
void solve()
{
depth.resize(n, -1);
dfs(0, -1, 0);
// keeps adding edges
// when next move is to remove edges do the following
// generate connected components, all nodes in the CC contains the same information, update the information before the cut
// to accomplish the following need the folling queries
// - add an edge
// - update the values for this connected component
// - remove an edge
// - query the value for a node
// important observations:
// use the root of the tree (one connected component), need a way to find this root without dfs?
// store the elemnts of a CC in a set or just the count is enough?
vector<int> ce, co;
ce.resize(n - 1, 0);
co.resize(n - 1, 0);
anc.resize(n); // anc[i] is the lowest (close to root) node in node i's connected component
info.resize(n);
for (int i = 0; i < n; i++)
{
anc[i] = i;
info[i] = 1;
}
//modifying the edges
for (int i = 0; i < m; i++)
{
ce[d[i]]++;
int a = edges[d[i]].first, b = edges[d[i]].second;
// note that a, b will never at the same depth for tree
if (ce[d[i]] & 1) // add edge d[i]
{
if (depth[anc[a]] > depth[anc[b]])
swap(a, b);
// merge b into a's connected field
info[anc[a]] += info[anc[b]] - co[d[i]]; // now put the count of info from b to a, remove the common info between a and b
info[anc[b]] = 0;
anc[b] = anc[a];
}
else // remove edge d[i]
{
if (depth[a] > depth[b])
swap(a, b);
// connected component with a still have the same root, b became the root of the other connected component
anc[b] = b;
info[b] = info[anc[a]];
// store the number of common nodes between CC a and CC b on edge
co[d[i]] = info[anc[a]];
}
}
// query
for (int i = 0; i < q; i++)
{
int a = c[i];
cout << info[anc[a]] << endl;
}
}
int main()
{
init("synchronization");
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
11772 KB |
Output is correct |
| 2 |
Correct |
51 ms |
11692 KB |
Output is correct |
| 3 |
Incorrect |
45 ms |
13624 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
249 ms |
14692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
