# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
120834 | songc | Mergers (JOI19_mergers) | C++14 | 161 ms | 43544 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int N, K, ans;
vector<int> adj[505050];
vector<int> rst[505050];
int S[505050], E[505050], num=1;
int st[505050], T[505050];
int P[22][505050], dep[505050];
int deg[505050], pa[505050];
void update(int t, int v){
while (t <= N){
T[t] += v;
t += t & -t;
}
}
int read(int t){
int ret=0;
while (t){
ret += T[t];
t ^= t & -t;
}
return ret;
}
int Find(int u){
if (u == pa[u]) return u;
return pa[u] = Find(pa[u]);
}
int dfs(int u, int p, int depth){
P[0][u] = p;
S[u] = num;
E[u] = num++;
dep[u] = depth;
for (int v : adj[u]){
if (v == p) continue;
E[u] = dfs(v, u, depth+1);
}
return E[u];
}
void Union(int u, int p){
if (read(E[u]) - read(S[u]-1) != 0) pa[Find(u)] = Find(p);
for (int v : adj[u]){
if (v == p) continue;
Union(v, u);
}
}
int LCA(int u, int v){
if (dep[u] < dep[v]) swap(u, v);
for (int i=20; i>=0; i--) if (dep[P[i][u]] >= dep[v]) u = P[i][u];
if (u == v) return u;
for (int i=20; i>=0; i--) if (P[i][u] != P[i][v]) u = P[i][u], v = P[i][v];
return P[0][u];
}
int main(){
int u, v;
scanf("%d %d", &N, &K);
for (int i=1; i<N; i++){
scanf("%d %d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i=1; i<=N; i++){
scanf("%d", &st[i]);
rst[st[i]].push_back(i);
}
dfs(1, 0, 1);
for (int i=1; i<=N; i++) update(i, 1);
for (int i=1; i<=20; i++) for (int j=1; j<=N; j++) P[i][j] = P[i-1][P[i-1][j]];
for (int i=1; i<=N; i++) pa[i] = i;
for (int i=1; i<=K; i++){
int lca = rst[i][0];
for (int j=1; j<(int)rst[i].size(); j++) lca = LCA(lca, rst[i][j]);
update(S[lca], -rst[i].size());
}
Union(1, 0);
for (int i=1; i<=N; i++) for (int j : adj[i]) if (Find(i) != Find(j)) deg[j]++;
for (int i=1; i<=N; i++) if (deg[i] == 1) ans++;
printf("%d", (ans+1)/2);
return 0;
}
Compilation message (stderr)
# | 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... |