#include <bits/stdc++.h>
#define z exit(0)
using namespace std;
const int N = 2e5 + 5;
set<int> H[N], s;
vector<int> g[N];
int sz[N], ded[N], have[N], fq[N], c[N], ct;
int fsz(int u, int p){ sz[u] = 1; for(int v: g[u]) if(!ded[v] && v != p) sz[u] += fsz(v, u); return sz[u];}
int fcen(int u, int p, int tsz){ for(int v: g[u]) if(!ded[v] && v != p && (sz[v]<<1) > tsz) return fcen(v, u, tsz); return u;}
void dfs(int u, int p){
++have[c[u]];
for(int v: g[u]) if(!ded[v] && v != p) dfs(v, u);
}
void efs(int u, int p){
--have[c[u]];
for(int v: g[u]) if(!ded[v] && v != p) efs(v, u);
}
void ffs(int u, int p){
++fq[c[u]]; s.insert(c[u]);
if(have[c[u]]){
//if(s.size() > H[c[u]].size()) swap(s, H[c[u]]);
H[c[u]].insert(s.begin(), s.end());
H[c[u]].insert(c[ct]);
}
for(int v: g[u]) if(!ded[v] && v != p) ffs(v, u);
if(!--fq[c[u]]) s.erase(c[u]);
}
void cd(int u){
ded[ct = u = fcen(u, -1, fsz(u, -1))] = 1;
dfs(u, u);
for(int v: g[u]) if(!ded[v]){ efs(v, u); s.clear(); ffs(v, u); dfs(v, u);}
efs(u, u);
for(int v: g[u]) if(!ded[v]) cd(v);
}
signed main(){
int n, k; scanf("%d %d", &n, &k);
for(int i = 0, u, v; i<n-1; ++i){
scanf("%d %d", &u, &v); --u; --v;
g[u].push_back(v); g[v].push_back(u);
}
for(int i = 0; i<n; ++i){ scanf("%d", c+i); --c[i];}
cd(0);
int mn = k;
for(int i = 0; i<k; ++i){
for(int x: H[i]) printf("%d ", x+1); puts("");
}
z;
for(int i = 0; i<k; ++i) mn = min(mn, (int)H[i].size() - 1);
printf("%d", mn);
}
Compilation message
capital_city.cpp: In function 'int main()':
capital_city.cpp:47:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
47 | for(int x: H[i]) printf("%d ", x+1); puts("");
| ^~~
capital_city.cpp:47:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
47 | for(int x: H[i]) printf("%d ", x+1); puts("");
| ^~~~
capital_city.cpp:38:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | int n, k; scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
capital_city.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%d %d", &u, &v); --u; --v;
| ~~~~~^~~~~~~~~~~~~~~~~
capital_city.cpp:43:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | for(int i = 0; i<n; ++i){ scanf("%d", c+i); --c[i];}
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
18268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
18268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
927 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
18268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
