| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 937033 | ParsaS | Synchronization (JOI13_synchronization) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 1e6 + 5;
int n, m, q;
vector<int> qr[N];
vector<pair<int, int> > adj[N];
bool mark[N];
int sz[N], ans[N];
int ver[N], E[N], szver, szE;
void dfs_sz(int& v, int p, int i = -1) {
sz[v] = 1;
ver[szver++] = v;
if (i >= 0) {
for (int j = 0; j < (int)qr[i].size(); j++)
E[szE++] = qr[i][j];
}
for (auto& a : adj[v]) {
if (!mark[a.fi] && a.fi != p) {
dfs_sz(a.fi, v, a.se);
sz[v] += sz[a.fi];
}
}
}
int find_centroid(int v, int S, int p = 0) {
for (auto [u, i] : adj[v]) {
if (!mark[u] && u != p && sz[u] * 2 > S) {
return find_centroid(u, S, v);
}
}
return v;
}
inline int get(int val) {
return lower_bound(E, E + szE, val) - E;
}
const int M = 1e9;
vector<int> vec[N];
int T;
pair<int*, int> st[M];
int stsz;
int inf = 1e9;
void rem(int S) {
while (stsz > S) {
*st[stsz-1].fi = st[stsz-1].se;
stsz--;
}
}
inline void SET(int& x, int y) {
if (y > inf || x == y) return;
//assert(stsz < M);
st[stsz++] = mp(&x, x);
x = y;
}
bool ISSUM;
int lz[N << 2], seg[N << 2];
void shift(int v, int tl, int tr) {
if (lz[v] == -1) return;
if ((lz[v]==0 && ISSUM) || tl == tr)
SET(seg[v], lz[v] * (tr - tl + 1));
if (tl < tr) {
SET(lz[v<<1], lz[v]);
SET(lz[v << 1 | 1], lz[v]);
}
SET(lz[v], -1);
}
void set_val(int l, int r, int val, int v = 1, int tl = 0, int tr = szE) {
if (l > r) return;
shift(v, tl, tr);
if (tl > r || tr < l) return;
if (tl >= l && tr <= r) {
SET(lz[v], val);
shift(v, tl, tr);
return;
}
int mid = (tl + tr) >> 1;
set_val(l, r, val, v << 1, tl, mid);
set_val(l, r, val, v << 1 | 1, mid + 1, tr);
SET(seg[v], seg[v << 1] + seg[v << 1 | 1]);
}
int query(int l, int r, int v = 1, int tl = 0, int tr = szE) {
if (l > r) return 0;
shift(v, tl, tr);
if (tl > r || tr < l) return 0;
if (tl >= l && tr <= r) {
return seg[v];
}
int mid = (tl + tr) >> 1;
return query(l, r, v << 1, tl, mid) + query(l, r, v << 1 | 1, mid + 1, tr);
}
void dfs2(int v, int i, int p = 0) {
int S = stsz;
int prv = -1;
for (int j = 0; j < (int)qr[i].size(); j += 2) {
int x = get(qr[i][j]);
set_val(get(prv + 1), x - 1, query(x, x));
prv = qr[i][j + 1];
}
set_val(get(prv + 1), get(m + 1), inf);
vec[T].pb(query(0, 0));
for (auto [u, j] : adj[v]) {
if (mark[u] || u == p) continue;
dfs2(u, j, v);
}
rem(S);
}
void dfs3(int v, int i, int p = 0) {
int S = stsz;
int prv = -1;
for (int j = 0; j < (int)qr[i].size(); j += 2) {
int x = get(qr[i][j]);
int y = query(get(prv + 1), x - 1) + query(x, x);
set_val(get(prv + 1), x - 1, 0);
set_val(x, x, y);
prv = qr[i][j + 1];
}
set_val(get(prv + 1), get(m + 1), 0);
ans[v] += query(0, get(m + 1));
for (auto [u, j] : adj[v]) {
if (mark[u] || u == p) continue;
dfs3(u, j, v);
}
rem(S);
}
void dfs(int v) {
rem(0);
szver = 0;
szE = 0;
E[szE++] = 0;
E[szE++] = m + 1;
E[szE++] = m + 2;
dfs_sz(v, 0);
int rt = find_centroid(v, sz[v]);
mark[rt] = 1;
sort(E, E + szE);
szE = unique(E, E + szE) - E;
int k = szE;
for (int i = 0; i < k; i++)
set_val(i, i, i);
int S = stsz;
for (auto [u, i] : adj[rt]) {
if (mark[u]) continue;
rem(S);
T = u;
vec[T].clear();
dfs2(u, i);
}
rem(0);
ISSUM = true;
set_val(0, 0, 1);
for (auto [u, i] : adj[rt]) {
if (mark[u]) continue;
for (auto x : vec[u]) {
if (x < inf)
set_val(x, x, query(x, x) + 1);
}
}
ans[rt] += query(0, m + 2);
for (auto [u, i] : adj[rt]) {
if (mark[u]) continue;
S = stsz;
for (auto x : vec[u])
if (x < inf)
set_val(x, x, query(x, x) - 1);
dfs3(u, i);
rem(S);
}
ISSUM = false;
for (auto [u, i] : adj[rt]) {
if (!mark[u]) dfs(u);
}
}
void solve() {
cin >> n >> m >> q;
for (int i = 1; i <= n - 1; i++) {
int v, u; cin >> v >> u;
adj[v].pb(mp(u, i)), adj[u].pb(mp(v, i));
}
for (int i = 1; i <= m; i++) {
int k; cin >> k;
qr[k].pb(i);
}
for (int i = 1; i < n; i++) {
if ((int)qr[i].size() % 2)
qr[i].pb(m + 1);
}
memset(lz, -1, sizeof lz);
dfs(1);
while (q--) {
int c; cin >> c;
cout << ans[c] << '\n';
}
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//freopen("input2.in", "r", stdin);
int tc = 1; // cin >> tc;
while (tc--) {
solve();
}
return 0;
}