#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
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 root;
vector < pair < int , int > > xx,yy;
vector < int > vis;
int xxx[100005];
int yyy[100005];
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)
{
vis.push_back(here);
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];
xxx[here]=2e9;
yyy[here]=2e9;
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,int fr)
{
if(what[here]==0) xxx[fr]=min(xxx[fr],deg);
if(what[here]==1) yyy[fr]=min(yyy[fr],deg);
for(auto i:Next[here])
{
if(!have[i]&&i!=fa)
{
if(fa==-1) DFS4(i,here,deg+1,i);
else DFS4(i,here,deg+1,fr);
}
}
}
void DFS5(int here,int fa,int deg,int fr)
{
if(what[here]==0)
{
if(xx[0].second==fr) con[here]=min(con[here],deg+xx[1].first);
else con[here]=min(con[here],deg+xx[0].first);
}
if(what[here]==1)
{
if(yy[0].second==fr) con[here]=min(con[here],deg+yy[1].first);
else con[here]=min(con[here],deg+yy[0].first);
}
for(auto i:Next[here])
{
if(!have[i]&&i!=fa)
{
if(fa==-1) DFS5(i,here,deg+1,i);
else DFS5(i,here,deg+1,fr);
}
}
}
void F2(int here)
{
vis.clear();
DFS2(here,-1);
nn=sz[here];
DFS3(here,-1);
xxx[0]=2e9;
yyy[0]=2e9;
DFS4(root,-1,0,0);
xx.clear();
yy.clear();
for(auto i:vis)
{
xx.push_back(make_pair(xxx[i],i));
yy.push_back(make_pair(yyy[i],i));
}
xx.push_back(make_pair(xxx[0],0));
yy.push_back(make_pair(yyy[0],0));
sort(xx.begin(),xx.end());
sort(yy.begin(),yy.end());
if(vis.size()==1)
{
have[root]=1;
return;
}
DFS5(root,-1,0,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--)
{
ok=0;
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(what[i]==-1) ok=1;
}
if(ok)
{
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:156:11: warning: unused variable 'M' [-Wunused-variable]
156 | int T,M,i,x=0,y=0,ok;
| ^
balancedtree.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
157 | scanf("%d",&T);
| ~~~~~^~~~~~~~~
balancedtree.cpp:162:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
162 | scanf("%d",&N);
| ~~~~~^~~~~~~~~
balancedtree.cpp:166:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
166 | scanf("%d %d",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~
balancedtree.cpp:172:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
172 | scanf("%d",&what[i]);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
29 ms |
2688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
2936 KB |
Output is correct |
| 2 |
Correct |
406 ms |
6740 KB |
Output is correct |
| 3 |
Correct |
275 ms |
3800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4051 ms |
2688 KB |
Time limit exceeded |
| 2 |
Execution timed out |
4045 ms |
12792 KB |
Time limit exceeded |
| 3 |
Execution timed out |
4022 ms |
6528 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4053 ms |
3456 KB |
Time limit exceeded |
| 2 |
Execution timed out |
4050 ms |
2688 KB |
Time limit exceeded |
| 3 |
Execution timed out |
4045 ms |
2816 KB |
Time limit exceeded |
| 4 |
Execution timed out |
4030 ms |
2688 KB |
Time limit exceeded |
| 5 |
Execution timed out |
4040 ms |
2688 KB |
Time limit exceeded |
| 6 |
Execution timed out |
4049 ms |
3192 KB |
Time limit exceeded |
| 7 |
Execution timed out |
4057 ms |
2688 KB |
Time limit exceeded |
| 8 |
Execution timed out |
4024 ms |
2688 KB |
Time limit exceeded |
| 9 |
Execution timed out |
4027 ms |
2688 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
29 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
124 ms |
2936 KB |
Output is correct |
| 4 |
Correct |
406 ms |
6740 KB |
Output is correct |
| 5 |
Correct |
275 ms |
3800 KB |
Output is correct |
| 6 |
Execution timed out |
4051 ms |
2688 KB |
Time limit exceeded |
| 7 |
Execution timed out |
4045 ms |
12792 KB |
Time limit exceeded |
| 8 |
Execution timed out |
4022 ms |
6528 KB |
Time limit exceeded |
| 9 |
Execution timed out |
4053 ms |
3456 KB |
Time limit exceeded |
| 10 |
Execution timed out |
4050 ms |
2688 KB |
Time limit exceeded |
| 11 |
Execution timed out |
4045 ms |
2816 KB |
Time limit exceeded |
| 12 |
Execution timed out |
4030 ms |
2688 KB |
Time limit exceeded |
| 13 |
Execution timed out |
4040 ms |
2688 KB |
Time limit exceeded |
| 14 |
Execution timed out |
4049 ms |
3192 KB |
Time limit exceeded |
| 15 |
Execution timed out |
4057 ms |
2688 KB |
Time limit exceeded |
| 16 |
Execution timed out |
4024 ms |
2688 KB |
Time limit exceeded |
| 17 |
Execution timed out |
4027 ms |
2688 KB |
Time limit exceeded |
| 18 |
Execution timed out |
4029 ms |
3192 KB |
Time limit exceeded |
| 19 |
Execution timed out |
4027 ms |
6652 KB |
Time limit exceeded |
| 20 |
Execution timed out |
4019 ms |
2688 KB |
Time limit exceeded |
| 21 |
Runtime error |
6 ms |
5248 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 22 |
Execution timed out |
4026 ms |
2688 KB |
Time limit exceeded |
