#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define _F "what"
using namespace std;
typedef long long ll;
constexpr int N = 1e5 + 1, M = 2e5 + 1;
int n, m, q;
vector<int> par(N, -1), sz(N, 1), lab(N, 1), pre(N), st[4*M], Q, L(N);
pair<int, int> E[N];
stack<pair<int, int>> rb;
int find_set(int u)
{
return (par[u] == -1 ? u : find_set(par[u]));
}
void merge_set(int i)
{
int u = find_set(E[i].fi), v = find_set(E[i].se);
if (u == v)
{
rb.push({-1, -1});
return;
}
else
{
if (sz[u] < sz[v])
swap(u, v);
int new_lab = lab[u] + lab[v] - pre[i];
lab[u] = new_lab;
par[v] = u;
sz[u] += sz[v];
rb.push({v, i});
}
}
void rollback()
{
auto p = rb.top(); rb.pop();
int v = p.fi, i = p.se;
if (v == -1)
return;
int u = par[v];
lab[v] = pre[i] = lab[u];
par[v] = -1;
sz[u] -= sz[v];
}
void add(int i, int l, int r, int tl = 1, int tr = m, int v = 1)
{
if (l > r)
return;
if (tl == l && tr == r)
st[v].pb(i);
else
{
int tm = (tl+tr)/2;
add(i, l, min(tm, r), tl, tm, 2*v);
add(i, max(l, tm+1), r, tm+1, tr, 2*v+1);
}
}
void dfs_st(int tl = 1, int tr = m, int v = 1)
{
for (int i: st[v])
merge_set(i);
if (tl == tr && tl == m)
for (int u: Q)
cout<<lab[find_set(u)]<<"\n";
else if (tl != tr)
{
int tm = (tl+tr)/2;
dfs_st(tl, tm, 2*v);
dfs_st(tm+1, tr, 2*v+1);
}
for (int i = 0; i < st[v].size(); ++i)
rollback();
}
void solve()
{
cin>>n>>m>>q;
Q.resize(q);
for (int i = 1; i < n; ++i)
cin>>E[i].fi>>E[i].se;
for (int i = 1; i <= m; ++i)
{
int x; cin>>x;
if (L[x] > 0)
{
add(x, L[x], i-1);
L[x] = 0;
}
else
L[x] = i;
}
for (int i = 1; i < n; ++i)
if (L[i] > 0)
add(i, L[i], m);
for (int i = 0; i < q; ++i)
cin>>Q[i];
dfs_st();
}
int main()
{
if (fopen(_F".INP", "r"))
{
freopen(_F".INP", "r", stdin);
freopen(_F".OUT", "w", stdout);
}
else if (fopen("test.inp", "r"))
{
freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
int Test = 1; //cin>>Test;
while (Test--) solve();
}
컴파일 시 표준 에러 (stderr) 메시지
synchronization.cpp: In function 'int main()':
synchronization.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | freopen(_F".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | freopen(_F".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | freopen("test.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |