#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
vector < int > Next[100005];
int what[100005];
int Ans[1000005];
int con[1000005];
int sz[1000005];
int ans=0,now,N,nn;
bool have[1000005];
int xx,yy,root;
void DFS(int st,int here,int fa,int deg)
{
if(st!=here) if(what[here]==what[st]) now=min(now,deg);
for(auto i:Next[here])
{
if(i!=fa)
{
DFS(st,i,here,deg+1);
}
}
}
void F(int here)
{
int t,i;
if(here==N+1)
{
t=0;
for(i=1;i<=N;i++)
{
now=2e9;
DFS(i,i,-1,0);
t=max(t,now);
}
ans=min(ans,t);
if(t==ans) for(i=1;i<=N;i++) Ans[i]=what[i];
}
else
{
if(what[here]==-1)
{
what[here]=1;
F(here+1);
what[here]=0;
F(here+1);
what[here]=-1;
}
else F(here+1);
}
}
int DFS2(int here,int fa)
{
sz[here]=1;
for(auto i:Next[here])
{
if(!have[i]&&i!=fa)
{
sz[here]+=DFS2(i,here);
}
}
return sz[here];
}
void DFS3(int here,int fa)
{
int t=nn-sz[here];
for(auto i:Next[here])
{
if(!have[i]&&i!=fa)
{
DFS3(i,here);
t=max(t,sz[i]);
}
}
if(t<=nn/2) root=here;
}
void DFS4(int here,int fa,int deg)
{
if(what[here]==0) xx=min(xx,deg);
if(what[here]==1) yy=min(yy,deg);
for(auto i:Next[here])
{
if(!have[i]&&i!=fa)
{
DFS4(i,here,deg+1);
}
}
}
void DFS5(int here,int fa,int deg)
{
if(what[here]==0) con[here]=min(con[here],deg+xx);
if(what[here]==1) con[here]=min(con[here],deg+yy);
for(auto i:Next[here])
{
if(!have[i]&&i!=fa)
{
DFS5(i,here,deg+1);
}
}
}
void F2(int here)
{
DFS2(here,-1);
nn=sz[here];
DFS3(here,-1);
xx=2e9;
yy=2e9;
DFS4(root,-1,0);
DFS5(root,-1,0);
have[root]=1;
for(auto i:Next[root]) if(!have[i]) F2(i);
}
int main()
{
int T,M,i,x=0,y=0,ok;
scanf("%d",&T);
while(T--)
{
ans=2e9;
scanf("%d",&N);
for(i=1;i<=N;i++) Next[i].clear();
for(i=1;i<N;i++)
{
scanf("%d %d",&x,&y);
Next[x].push_back(y);
Next[y].push_back(x);
}
for(i=1;i<=N;i++) scanf("%d",&what[i]);
if(N<=17)
{
F(1);
if(ans==2000000000) printf("-1\n");
else
{
printf("%d\n",ans);
for(i=1;i<=N;i++) printf("%d ",Ans[i]);
printf("\n");
}
}
else
{
x=0;
y=0;
for(i=1;i<=N;i++)
{
have[i]=0;
con[i]=2e9;
if(what[i]==1) x++;
else y++;
}
if(x==1||y==1) printf("-1\n");
else
{
ans=0;
F2(1);
for(i=1;i<=N;i++) ans=max(ans,con[i]);
printf("%d\n",ans);
for(i=1;i<=N;i++) printf("%d ",what[i]);
printf("\n");
}
}
}
return 0;
}
Compilation message
balancedtree.cpp: In function 'int main()':
balancedtree.cpp:121:11: warning: unused variable 'M' [-Wunused-variable]
121 | int T,M,i,x=0,y=0,ok;
| ^
balancedtree.cpp:121:23: warning: unused variable 'ok' [-Wunused-variable]
121 | int T,M,i,x=0,y=0,ok;
| ^~
balancedtree.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
122 | scanf("%d",&T);
| ~~~~~^~~~~~~~~
balancedtree.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
126 | scanf("%d",&N);
| ~~~~~^~~~~~~~~
balancedtree.cpp:130:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
130 | scanf("%d %d",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~
balancedtree.cpp:134:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
134 | for(i=1;i<=N;i++) scanf("%d",&what[i]);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
27 ms |
2688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
2936 KB |
Output isn't correct |
| 2 |
Incorrect |
212 ms |
5368 KB |
Output isn't correct |
| 3 |
Incorrect |
138 ms |
3448 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
2936 KB |
Output isn't correct |
| 2 |
Incorrect |
232 ms |
13176 KB |
Output isn't correct |
| 3 |
Incorrect |
126 ms |
7160 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
168 ms |
3832 KB |
Output isn't correct |
| 2 |
Incorrect |
105 ms |
3192 KB |
Output isn't correct |
| 3 |
Incorrect |
104 ms |
3064 KB |
Output isn't correct |
| 4 |
Incorrect |
72 ms |
2936 KB |
Output isn't correct |
| 5 |
Incorrect |
80 ms |
3064 KB |
Output isn't correct |
| 6 |
Incorrect |
113 ms |
3168 KB |
Output isn't correct |
| 7 |
Incorrect |
111 ms |
2936 KB |
Output isn't correct |
| 8 |
Incorrect |
73 ms |
2880 KB |
Output isn't correct |
| 9 |
Incorrect |
79 ms |
2936 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
27 ms |
2688 KB |
Output is correct |
| 3 |
Incorrect |
81 ms |
2936 KB |
Output isn't correct |
| 4 |
Incorrect |
212 ms |
5368 KB |
Output isn't correct |
| 5 |
Incorrect |
138 ms |
3448 KB |
Output isn't correct |
| 6 |
Incorrect |
88 ms |
2936 KB |
Output isn't correct |
| 7 |
Incorrect |
232 ms |
13176 KB |
Output isn't correct |
| 8 |
Incorrect |
126 ms |
7160 KB |
Output isn't correct |
| 9 |
Incorrect |
168 ms |
3832 KB |
Output isn't correct |
| 10 |
Incorrect |
105 ms |
3192 KB |
Output isn't correct |
| 11 |
Incorrect |
104 ms |
3064 KB |
Output isn't correct |
| 12 |
Incorrect |
72 ms |
2936 KB |
Output isn't correct |
| 13 |
Incorrect |
80 ms |
3064 KB |
Output isn't correct |
| 14 |
Incorrect |
113 ms |
3168 KB |
Output isn't correct |
| 15 |
Incorrect |
111 ms |
2936 KB |
Output isn't correct |
| 16 |
Incorrect |
73 ms |
2880 KB |
Output isn't correct |
| 17 |
Incorrect |
79 ms |
2936 KB |
Output isn't correct |
| 18 |
Incorrect |
574 ms |
4316 KB |
Output isn't correct |
| 19 |
Incorrect |
1800 ms |
8540 KB |
Output isn't correct |
| 20 |
Incorrect |
353 ms |
3704 KB |
Output isn't correct |
| 21 |
Runtime error |
6 ms |
5248 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 22 |
Runtime error |
203 ms |
5752 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
