#include <bits/stdc++.h>
using namespace std;
int N;
int M;
vector<int> adjlst[200100];
int u,v;
int parent[200100];
int lst[200100];
int d1,d2;
bool diam[200100];
int d[200100];
int md[200100];
int pre[200100];
vector<int> path[200100];
int h;
long long int ans[200100];
int c;
int num;
vector<pair<int,int>> uni;
map<int,int> tooken;
//3Na 3Si 3Al 12O
void dfs(int i, int p, int de){
d[i] = de;
md[i] = de;
parent[i] = p;
for(int j : adjlst[i]){
if(j == p) continue;
dfs(j, i, de + 1);
md[i] = max(md[i],md[j]);
}
}
void solve(int i, int pa);
void recurse(int i, int j, int pa){
uni.push_back({d[i],i});
auto it = lower_bound(uni.begin(),uni.end(),make_pair(pa,-1) );
vector<int> undo;
int pa1 = d[i] + 1 - (md[j] - d[i] - 1);
while(it != uni.end() && it -> first < pa1){
undo.push_back(lst[it -> second]);
tooken[lst[it -> second]]++;
advance(it,1);
}
solve(j,max(pa1,pa));
uni.pop_back();
reverse(undo.begin(),undo.end());
for(int i : undo){
tooken[i]--;
if(tooken[i] == 0) tooken.erase(i);
}
}
void solve(int i, int pa){//printf("i: %d\n",i);
if(d[i] <= d[c]){
int child = -1;
for(int j : path[i]){
if(j != parent[i]) child = j;
}
int num1 = d[i];
for(int j : adjlst[i]){
if(j == child || j == parent[i]) continue;
num1 = max(num1,md[j]);
}
while(!uni.empty() && uni.back().first >= d[i] - (num1 - d[i]) ){
uni.pop_back();
}
uni.push_back({d[i],i});
if(d[i] == d[c]){
int h = d[i] + 1 - (num - d[i] - 1);
int it = 0;
while(it != uni.size() && uni[it].first < h){
tooken[lst[uni[it].second]]++;
it++;
}
solve(child,h);
}
else solve(child,2);
}
else{
/*if(i == 0){
for(pair<int,int> ii : tooken){
printf("t %d %d\n",ii.first,ii.second);
}
}*/
map<int,int,greater<int>> mep;
for(int j : adjlst[i]){
if(j == parent[i]) continue;
mep[md[j]]++;
}
ans[i] = tooken.size();
if(mep.empty()) return;
if(mep.begin() -> second == 1){
int special;
for(int j : adjlst[i]){
if(j == parent[i]) continue;
if(md[i] == md[j]) special = j;
}
auto it1 = mep.begin();
advance(it1,1);
int num;
vector<int> undo1;
if(it1 != mep.end()){
num = d[i] - (it1 -> first - d[i]);
while(!uni.empty() && uni.back().first >= num){
if(uni.back().first < pa){
tooken[uni.back().second]--;
if(tooken[uni.back().second] == 0) tooken.erase(uni.back().second);
}
undo1.push_back(uni.back().second);
uni.pop_back();
}
}
uni.push_back({d[i],i});
auto it = lower_bound(uni.begin(),uni.end(),make_pair(pa,-1));
vector<int> undo;
int pa1 = d[i] + 1 - (md[special] - d[i] - 1);
//printf("%d\n",uni.back().first);
while(it != uni.end() && it -> first < pa1){
undo.push_back(lst[it -> second]);
tooken[lst[it -> second]]++;
advance(it,1);
}
solve(special,max(pa,pa1));
uni.pop_back();
reverse(undo.begin(),undo.end());
for(int i : undo){
tooken[i]--;
if(tooken[i] == 0) tooken.erase(i);
}
while(!uni.empty() && uni.back().first >= num){
if(uni.back().first < pa){
tooken[uni.back().second]--;
if(tooken[uni.back().second] == 0) tooken.erase(uni.back().second);
}
undo1.push_back(uni.back().second);
uni.pop_back();
}
for(int j : adjlst[i]){
if(j == parent[i]) continue;
if(md[j] == md[i]) continue;
int num;
num = d[i] - (md[i] - d[i]);
recurse(i,j,pa);
}
reverse(undo1.begin(),undo1.end());
for(int i : undo1){
uni.push_back({d[i],i});
if(uni.back().first < pa){
tooken[uni.back().second]++;
}
}
}
else{
vector<int> undo1;
int num = d[i] - (md[i] - d[i]);
while(!uni.empty() && uni.back().first >= num){
if(uni.back().first < pa){
tooken[uni.back().second]--;
if(tooken[uni.back().second] == 0) tooken.erase(uni.back().second);
}
undo1.push_back(uni.back().second);
uni.pop_back();
}
for(int j : adjlst[i]){
if(j == parent[i]) continue;
recurse(i,j,pa);
}
reverse(undo1.begin(),undo1.end());
for(int i : undo1){
uni.push_back({d[i],i});
if(uni.back().first < pa){
tooken[uni.back().second]++;
}
}
}
}
}
int main(){
scanf(" %d",&N);
scanf(" %d",&M);
for(int i = 0; i < N - 1; i++){
scanf(" %d",&u);
scanf(" %d",&v);
u--;
v--;
adjlst[u].push_back(v);
adjlst[v].push_back(u);
}
for(int i = 0; i < N; i++){
scanf(" %d",&lst[i]);
lst[i]--;
}
dfs(1,-1,0);
pair<int,int> ii = {0,-1};
for(int i = 0; i < N; i++){
ii = max(ii, {d[i],i});
ans[i] = 0;
}
d1 = ii.second;
dfs(d1,-1,0);
ii = {0,-1};
for(int i = 0; i < N; i++){
ii = max(ii, {d[i],i});
}
d2 = ii.second;
num = ii.first;
h = d2;
for(int i = 0; i < num; i++){
path[h].push_back(parent[h]);
path[parent[h]].push_back(h);
h = parent[h];
}
if(num % 2 == 1){
//printf("%d %d\n",d1,d2);
c = d2;
for(int i = 0; i < num / 2 + 1; i++){
c = parent[c];
}
solve(d1,0);
//printf("S");
dfs(d2,-1,0);
c = d1;
for(int i = 0; i < num / 2 + 1; i++){
c = parent[c];
}
uni.clear();
tooken.clear();
solve(d2,0);
//printf("S\n\n");
}
else{
//printf("%d %d\n",d1,d2);
c = d2;
for(int i = 0; i < num / 2 + 1; i++){
c = parent[c];
}
solve(d1,0);
//printf("S");
dfs(d2,-1,0);
c = d1;
for(int i = 0; i < num/2 + 1; i++){
c = parent[c];
}
uni.clear();
tooken.clear();
solve(d2,0);
//printf("S\n\n");
}
for(int i = 0; i < N; i++){
printf("%d\n",ans[i]);
}
}
/*
6 4
6 1
1 2
2 3
3 4
3 5
1 2 1 2 4 4
4 4
1 2
1 3
1 4
1 2 3 4
7 7
1 2
1 3
1 4
2 5
3 6
4 7
1 2 3 4 5 6 7
5 1
2 1
3 1
4 1
5 3
1 1 1 1 1
*/
Compilation message
joi2019_ho_t5.cpp: In function 'void solve(int, int)':
joi2019_ho_t5.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | while(it != uni.size() && uni[it].first < h){
| ~~~^~~~~~~~~~~~~
joi2019_ho_t5.cpp:171:21: warning: variable 'num' set but not used [-Wunused-but-set-variable]
171 | int num;
| ^~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:309:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
309 | printf("%d\n",ans[i]);
| ~^ ~~~~~~
| | |
| int long long int
| %lld
joi2019_ho_t5.cpp:216:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
216 | scanf(" %d",&N);
| ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:217:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
217 | scanf(" %d",&M);
| ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:220:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
220 | scanf(" %d",&u);
| ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:221:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
221 | scanf(" %d",&v);
| ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:230:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
230 | scanf(" %d",&lst[i]);
| ~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'void solve(int, int)':
joi2019_ho_t5.cpp:158:32: warning: 'num' may be used uninitialized in this function [-Wmaybe-uninitialized]
158 | while(!uni.empty() && uni.back().first >= num){
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:149:18: warning: 'special' may be used uninitialized in this function [-Wmaybe-uninitialized]
149 | solve(special,max(pa,pa1));
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
15184 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
15440 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
19784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
111 ms |
20808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
15184 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
15440 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
