#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 12, MOD = (int)1e9 + 7;
int n,m,c[N],d1,d2;
vector<int> g[N];
int f(int v) {
queue<int> q;
vector<bool> vis(n + 1,0);
q.push(v);
vis[v] = 1;
int ret;
while(!q.empty()) {
int u = q.front();
ret = u;
q.pop();
for(int to:g[u]) {
if(!vis[to]) {
q.push(to);
vis[to] = 1;
}
}
}
return ret;
}
int dp[N],zap = 0;
void solve(int x,int y) {
zap++;
vector<bool> ok(n + 1,0),l(n+1,1);
vector<int> dep(n+1,0),path,di(n + 1,0),col(n + 1,0);
function<void(int,int)> prec = [&](int v,int pr){
for(int to:g[v]) {
if(to == pr) continue;
l[v] = false;
dep[to] = dep[v] + 1;
prec(to,v);
ok[v] = (ok[v] | ok[to]);
}
if(v == y) {
ok[v] = 1;
}
if(ok[v]) {
path.push_back(v);
}
};
dep[x] = 1;
prec(x,-1);
queue<int> q;
di[y] = 1;
q.push(y);
while(!q.empty()) {
int v = q.front();
q.pop();
col[di[v]]++;
for(int to:g[v]) {
if(!di[to]) {
di[to] = di[v] + 1;
q.push(to);
}
}
}
map<int,int> cc;
set<pair<int,int>> d;
for(int i = 1;i <= n;i++) {
if(i != y && col[di[i]] == 1) {
d.insert({dep[i],c[i]});
cc[c[i]]++;
}
}
int cur = 0;
function<void(int,int)> paint = [&](int v,int pr){
vector<int> a;
for(int to:g[v]) {
if(ok[to] || to == pr) continue;
a.push_back(to);
}
if((int)a.size() == 1) {
}
};
for(int i = 0;i < (int)path.size();i++) {
assert(cur == dep[y] - dep[path[i]]);
int v = path[i];
while(!d.empty()) {
int val = dep[v] - ((*d.rbegin()).first);
if(val <= cur) {
auto [_d,co] = (*d.rbegin());
cc[co]--;
if(cc[co] == 0) {
cc.erase(co);
}
d.erase(*d.rbegin());
} else break;
}
if((int)cc.size()){
dp[v] = (int)cc.size();
}
cur++;
}
}
bool is[N],l[N];
void go(int v,int pr = -1) {
l[v] = 1;
for(int to:g[v]) {
if(to == pr) continue;
l[v] = false;
go(to,v);
is[v] = (is[v] | is[to]);
}
if(v == d2) {
is[v] = 1;
}
}
void test() {
cin >> n >> m;
for(int i = 1; i <= n - 1; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
for(int i = 1; i <= n; i++) {
cin >> c[i];
}
d1 = f(1),d2 = f(d1);
memset(dp,-1,sizeof(dp));
solve(d1,d2);
solve(d2,d1);
// go(d1);
for(int i = 1; i <= n; i++) {
cout << i << ' ' << dp[i] << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int t = 1;
// cin >> t;
while(t--) {
test();
}
}
Compilation message
joi2019_ho_t5.cpp: In function 'int f(int)':
joi2019_ho_t5.cpp:27:12: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
27 | return ret;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
27736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
35080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
39828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
27736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
