#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int n, m;
vector<int> t[maxn], cit[maxn];
int sz[maxn], st[maxn], h[maxn], par[maxn][18], up[maxn], Time = 0, inPlace[maxn];
int Grand[maxn], col[maxn];
int lca(int v, int u){
if (h[v] < h[u])
swap(v, u);
for (int i = 17; i >= 0; i--)
if (h[v] - (1 << i) >= h[u])
v = par[v][i];
if (v == u)
return v;
for (int i = 17; i >= 0; i--)
if (par[v][i] != par[u][i])
v = par[v][i], u = par[u][i];
return par[v][0];
}
int dis(int v, int u){
return h[v] + h[u] - 2*h[lca(v,u)];
}
int seg[4*maxn], lazy[4*maxn];
void shift(int,int,int);
int get(int id, int L, int R, int l, int r){
if (r <= L or R <= l or seg[id] == 0)
return -1;
if (L+1 == R)
return L;
shift(id, L, R);
int mid = (L + R) >> 1;
int ret = get(2*id+0, L, mid, l, r);
if (ret != -1)
return ret;
return get(2*id+1, mid, R, l, r);
}
void change(int id, int L, int R, int l, int r, int val){
if (r <= L or R <= l)
return;
if (l <= L and R <= r){
seg[id] = val;
lazy[id] = val;
return;
}
shift(id, L, R);
int mid = (L + R) >> 1;
change(2*id+0, L, mid, l, r, val);
change(2*id+1, mid, R, l, r, val);
seg[id] = max(seg[2*id+0], seg[2*id+1]);
}
void shift(int id, int L, int R){
if (lazy[id] == -1)
return;
int mid = (L + R) >> 1;
change(2*id+0, L, mid, L, mid, lazy[id]);
change(2*id+1, mid, R, mid, R, lazy[id]);
lazy[id] = -1;
}
int cmpCount, distinctColor[maxn];
vector<int> cmp[maxn], topol;
bool visited[maxn];
void dfs(int c, bool w){
visited[c] = 1;
for (auto it : cit[c]){
int v = it;
change(1, 0, n, st[v], st[v]+1, 0);
while (v != -1 and h[v] > h[Grand[c]]){
int l = (h[up[v]] >= h[Grand[c]] ? st[up[v]] : st[Grand[c]]), r = st[v]+1;
int idx = get(1, 0, n, l, r);
if (idx == -1){
v = par[up[v]][0];
continue;
}
change(1, 0, n, idx, idx+1, 0);
if (!visited[col[inPlace[idx]]])
dfs(col[inPlace[idx]], w);
}
}
if (w == 0)
topol.push_back(c);
else{
for (auto v : cit[c])
cmp[cmpCount].push_back(v);
distinctColor[cmpCount] ++;
}
}
void SCC(){
change(1, 0, n, 0, n, 1);
for (int i = 1; i <= m; i++)
if (!visited[i])
dfs(i, 0);
change(1, 0, n, 0, n, 1);
memset(visited, 0, sizeof visited);
for (auto i : topol)
if (!visited[i])
dfs(i, 1), cmpCount ++;
}
void dfs1(int v, int p = -1){
par[v][0] = p;
for (int i = 1; par[v][i-1] != -1 and i < 18; i++)
par[v][i] = par[par[v][i-1]][i-1];
st[v] = Time, inPlace[Time++] = v;
bool bigChild = true;
for (auto u : t[v]){
h[u] = h[v] + 1;
if (bigChild)
up[u] = up[v];
else
up[u] = u;
bigChild = false;
dfs1(u, v);
}
}
int dfssz(int v, int par = -1){
for (int i = 0; i < t[v].size(); i++)
if (t[v][i] == par)
t[v].erase(t[v].begin() + i);
sz[v] = 1;
for (auto u : t[v])
sz[v] += dfssz(u, v);
sort(t[v].begin(), t[v].end(), [](int a, int b){return sz[a] > sz[b];});
return sz[v];
}
int main(){
ios_base::sync_with_stdio(false);
cin >> n >> m;
for (int i = 0; i < n-1; i++){
int v, u;
cin >> v >> u;
t[v].push_back(u);
t[u].push_back(v);
}
dfssz(1);
memset(par, -1, sizeof par);
up[1] = 1;
dfs1(1);
for (int i = 1; i <= n; i++){
int c;
cin >> c;
col[i] = c;
cit[c].push_back(i);
}
for (int i = 1; i <= m; i++){
sort(cit[i].begin(), cit[i].end(), [](int a, int b){return st[a] < st[b];});
Grand[i] = cit[i][0];
for (auto v : cit[i])
Grand[i] = lca(Grand[i], v);
}
SCC();
int answer = m-1;
for (int i = 0; i < cmpCount; i++){
sort(cmp[i].begin(), cmp[i].end(), [](int a, int b){return st[a] < st[b];});
int cnt = 0;
for (int j = 0; j < cmp[i].size(); j++){
int v = cmp[i][j];
if (j+1 < cmp[i].size())
cnt += dis(v, cmp[i][j+1]);
else
cnt += dis(v, cmp[i][0]);
}
cnt = (cnt+2) / 2;
if (cnt == cmp[i].size())
answer = min(answer, distinctColor[i]-1);
}
cout << 0 << endl;
}
Compilation message
capital_city.cpp: In function 'int dfssz(int, int)':
capital_city.cpp:130:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < t[v].size(); i++)
~~^~~~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:170:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < cmp[i].size(); j++){
~~^~~~~~~~~~~~~~~
capital_city.cpp:172:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (j+1 < cmp[i].size())
~~~~^~~~~~~~~~~~~~~
capital_city.cpp:178:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (cnt == cmp[i].size())
~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
28796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
28796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
906 ms |
70280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
28796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
