이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[500002], col[500002], tree[500002];
vector<pair<int, int>> edge;
int anc[500002], co[500002], d[500002], spr[500002][20];
int link[500002], lcacol[500002];
int ans = 0;
int _find(int x)
{
if(x == link[x]) return x;
return link[x] = _find(link[x]);
}
void _unite(int x, int y)
{
x = _find(x);
y = _find(y);
link[x] = y;
}
void dep(int x, int p)
{
for(int i : adj[x])
{
if(i == p) continue;
d[i] = d[x] + 1;
spr[i][0] = x;
dep(i, x);
}
}
void init(int n)
{
for(int t=1;t<20;t++) for(int i=1;i<=n;i++)
spr[i][t] = spr[spr[i][t-1]][t-1];
}
int lca(int a, int b)
{
if(d[a] < d[b]) swap(a, b);
int dif = d[a] - d[b];
for(int i=19;i>=0;i--) if((1<<i) & dif) a = spr[a][i];
if(a == b) return a;
for(int i=19;i>=0;i--)
{
if(spr[a][i] != spr[b][i] && spr[a][i] != 0 && spr[b][i] != 0)
{
a = spr[a][i];
b = spr[b][i];
}
}
return spr[a][0];
}
int dfs(int x, int p)
{
int ret = lcacol[co[x]];
for(int i : adj[x])
{
if(i == p) continue;
int tmp = dfs(i, x);
if(tmp > d[x]) edge.push_back({i, x});
else _unite(i, x);
ret = min(ret, tmp);
}
return ret;
}
void solve(int x, int p)
{
int ret = 0;
for(int i : tree[x])
{
if(i == p) continue;
solve(i, x);
ret++;
}
ans += ret/2;
if(p == -1 && ret%2 == 1) ans++;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, k; cin >> n >> k;
for(int i=1;i<n;i++)
{
int s, e; cin >> s >> e;
adj[s].push_back(e);
adj[e].push_back(s);
}
for(int i=1;i<=n;i++) link[i] = i;
d[1] = 1; dep(1, -1); init(n);
for(int i=1;i<=n;i++)
{
int c; cin >> c;
co[i] = c;
col[c].push_back(i);
}
for(int i=1;i<=k;i++)
{
lcacol[i] = col[i][0];
for(int j = 1; j < col[i].size();j++)
{
lcacol[i] = lca(lcacol[i], col[i][j]);
}
lcacol[i] = d[lcacol[i]];
}
dfs(1, -1);
for(auto u : edge)
{
int s = u.first, e = u.second;
s = _find(s); e = _find(e);
tree[s].push_back(e);
tree[e].push_back(s);
}
solve(_find(1), -1);
cout << ans;
}
컴파일 시 표준 에러 (stderr) 메시지
mergers.cpp: In function 'int main()':
mergers.cpp:117:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int j = 1; j < col[i].size();j++)
| ~~^~~~~~~~~~~~~~~
# | 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... |