#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define all(x) (x).begin(),(x).end()
int main() {
int n,m;scanf("%d%d",&n,&m);
vector<vector<int>> adj(n);
for(int i=1;i<n;i++) {
int u,v;scanf("%d%d",&u,&v);u--;v--;
adj[u].push_back(v); adj[v].push_back(u);
}
vector<int> c(n);for(auto&x:c)scanf("%d",&x),x--;
// ;-;
vector<int> sz(n),dep(n),mxdep(n),val(n);
auto dfs1 = [&](auto self, int v, int p=-1, int rk=0) -> void {
sz[v]=1; dep[v]=rk; mxdep[v]=0;
for(auto x:adj[v]) if(x!=p)
self(self,x,v,rk+1),
sz[v]+=sz[x],
mxdep[v]=max(mxdep[v],mxdep[x]+1);
};
vector<int> S(m); int cnt=0;
auto add = [&](int x, int d) {
// printf("\t\tadd %d %d\n",x,d);
cnt-=S[x]>0;
S[x]+=d;
cnt+=S[x]>0;
};
vector<int> A;
vector<array<int,2>> B;
auto dfs2 = [&](auto self, int v, int p=-1) -> void {
sort(all(adj[v]), [&](int a, int b) { return mxdep[a] > mxdep[b]; });
assert(p == -1 || adj[v][0] == p);
if(p==-1) adj[v].insert(adj[v].begin(),-1);
// printf("%d: ", v);
// for(auto x:A)printf("%d ",x);
// printf("\n");
// for(auto x:B)printf("%d|%d ", x[0],x[1]);
// printf("\n");
vector<array<int,2>> R;
for(int i=1;i<adj[v].size();i++) {
int x = adj[v][i];
int d=0;
if(i > 1) d=mxdep[adj[v][1]]+1;
else if(adj[v].size() > 2) d=mxdep[adj[v][2]]+1;
// printf("\t\t\tv=%d x=%d d=%d\n",v,x,d);
// printf("\t\t\tcut %d\n", dep[v]-d);
while(B.size() && B.back()[0] >= dep[v] - d) {
R.push_back(B.back());
add(B.back()[1], -1);
B.pop_back();
}
B.push_back({dep[v], c[v]});
add(c[v],1);
A.push_back(d);
self(self, x, v);
A.pop_back();
B.pop_back();
add(c[v],-1);
}
if(adj[v].size()>1) {
int d=mxdep[adj[v][1]]+1;
// printf("\t\t\texit d=%d\n", adj[v][1]);
while(B.size() && B.back()[0] >= dep[v] - d) {
R.push_back(B.back());
add(B.back()[1], -1);
B.pop_back();
}
}
// printf("%d exit: ", v);
// for(auto x:A)printf("%d ",x);
// printf("(%d)\n", adj[v].size()>1?adj[v][1]:0);
// for(auto x:B)printf("%d|%d ", x[0],x[1]);
// printf("\n");
// for(int i=0;i<m;i++)printf("%d ",S[i]);
// printf("\n");
val[v] = max(val[v],cnt);
/*while(R.size()) {
B.push_back(R.back());
add(B.back()[1], 1);
R.pop_back();
}*/
if(p==-1)adj[v].erase(adj[v].begin());
};
// find dia
dfs1(dfs1, 0);
int v1 = max_element(all(dep)) - dep.begin();
dfs1(dfs1, v1);
int v2 = max_element(all(dep)) - dep.begin();
// printf("dia is %d, %d\n", v1, v2);
dfs2(dfs2,v1);
dfs1(dfs1,v2);
dfs2(dfs2,v2);
for(int i=0;i<n;i++)printf("%d ",val[i]);
printf("\n");
}
Compilation message
joi2019_ho_t5.cpp: In instantiation of 'main()::<lambda(auto:2, int, int)> [with auto:2 = main()::<lambda(auto:2, int, int)>]':
joi2019_ho_t5.cpp:107:21: required from here
joi2019_ho_t5.cpp:50:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=1;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:9:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | int n,m;scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp:13:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | int u,v;scanf("%d%d",&u,&v);u--;v--;
| ~~~~~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp:17:44: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | vector<int> c(n);for(auto&x:c)scanf("%d",&x),x--;
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
1240 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
76 ms |
19256 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
82 ms |
27672 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
1240 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
