#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
typedef long long ll;
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;
#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (100006)
ll t,n;
int st[MAXN],en[MAXN],co,depth[MAXN],C[MAXN],bck[MAXN];
vector<int>v[MAXN],dk;
struct node {
int s,e,m,b;
ll v,add;
node*l,*r;
node(int S,int E,ll bb){
s=S,e=E,m=(s+e)>>1;
v=0,add=0,b=bb;
if(s^e)l=new node(s,m,bb),r=new node(m+1,e,bb);
}
void update(int x,int y,ll nval){
value();
if(s==x&&e==y){add+=nval;return;}
if(x>m)r->update(x,y,nval);
else if(y<=m)l->update(x,y,nval);
else l->update(x,m,nval),r->update(m+1,y,nval);
v=min(l->value(),r->value());
}
ll value(){
v+=add;
if(s^e){
l->add+=add;
r->add+=add;
}
add=0;
return v;
}
ll rmq(int x,int y){
if(x>y)return LLINF;
value();
if(s==x&&e==y)return v;
if(x>m)return r->rmq(x,y);
else if(y<=m)return l->rmq(x,y);
else return min(l->rmq(x,m),r->rmq(m+1,y));
}
void reset(){
v=add=0;
if(s^e)l->reset(),r->reset(),v=min(l->v,r->v);
else v=((s<=n-1&&(C[bck[s]]==b))?depth[bck[s]]:LLINF);
}
void pt(){
// cerr<<s<<' '<<e<<' '<<v<<' '<<bck[s]<<' '<<b<<'\n';
// if(s^e) l->pt(),r->pt();
}
} *seg[2];
void dfs(int x,int p){
bck[co]=x, st[x]=co++;
for(auto i:v[x])if(i^p){
depth[i]=depth[x]+1, dfs(i,x);
}
en[x]=co-1;
}
ll mx;
void check(int x,int p){
mx=max(mx,min(seg[C[x]]->rmq(0,st[x]-1),seg[C[x]]->rmq(st[x]+1,n-1)));
for(auto i:v[x])if(i^p){
FOR(j,0,1) seg[j]->update(0,co-1,1),seg[j]->update(st[i],en[i],-2);
check(i,x);
FOR(j,0,1) seg[j]->update(0,co-1,-1),seg[j]->update(st[i],en[i],2);
}
}
ll get_ans() {
FOR(i,1,n)assert(C[i]!=-1);
seg[0]->reset(),seg[1]->reset();
mx=0;
check(1,1);
return mx;
}
void st1() {
ll ans=n+1, bruh=0;
FOR(i,0,(1<<siz(dk))-1){
FOR(j,0,siz(dk)-1){
C[dk[j]]=bool((1<<j)&i);
}
ll en=get_ans();
if(en<ans)bruh=i;
ans=min(ans, en);
}
cout<<(ans>=n+1?-1:ans)<<'\n';
if(ans>=n+1)return;
FOR(j,0,siz(dk)-1){
C[dk[j]]=bool((1<<j)&bruh);
}
FOR(j,1,n)cout<<C[j]<<' ';cout<<'\n';
}
void solve(){
cin>>n;
FOR(i,0,n)v[i].clear();
dk.clear();
FOR(i,0,n)st[i]=en[i]=co=depth[i]=C[i]=bck[i]=0;
seg[0]=new node(0, n-1, 0), seg[1]=new node(0, n-1, 1);
FOR(i,0,n-2){
ll a,b;cin>>a>>b;
v[a].eb(b),v[b].eb(a);
}
FOR(i,1,n){cin>>C[i];if(C[i]==-1)dk.pb(i);}
dfs(1,1);
if(*min_element(C+1,C+n+1)==-1){
st1();
return;
}
ll en=get_ans();
cout<<(en>=n+1 ? -1 : en)<<'\n';
if(en>=n+1)return;
FOR(i,1,n)cout<<C[i]<<' ';cout<<'\n';
}
int main(){
FAST
cin>>t;
while(t--)solve();
}
Compilation message
balancedtree.cpp: In function 'void st1()':
balancedtree.cpp:23:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
^
balancedtree.cpp:115:2: note: in expansion of macro 'FOR'
FOR(j,1,n)cout<<C[j]<<' ';cout<<'\n';
^~~
balancedtree.cpp:115:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
FOR(j,1,n)cout<<C[j]<<' ';cout<<'\n';
^~~~
balancedtree.cpp: In function 'void solve()':
balancedtree.cpp:23:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
^
balancedtree.cpp:136:2: note: in expansion of macro 'FOR'
FOR(i,1,n)cout<<C[i]<<' ';cout<<'\n';
^~~
balancedtree.cpp:136:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
FOR(i,1,n)cout<<C[i]<<' ';cout<<'\n';
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
3960 KB |
Output is correct |
| 2 |
Correct |
66 ms |
4728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
165 ms |
28408 KB |
Output is correct |
| 2 |
Correct |
338 ms |
30712 KB |
Output is correct |
| 3 |
Correct |
274 ms |
28536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4081 ms |
2944 KB |
Time limit exceeded |
| 2 |
Execution timed out |
4066 ms |
44932 KB |
Time limit exceeded |
| 3 |
Execution timed out |
4058 ms |
22520 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4062 ms |
8952 KB |
Time limit exceeded |
| 2 |
Execution timed out |
4070 ms |
3072 KB |
Time limit exceeded |
| 3 |
Execution timed out |
4067 ms |
6008 KB |
Time limit exceeded |
| 4 |
Execution timed out |
4096 ms |
2816 KB |
Time limit exceeded |
| 5 |
Execution timed out |
4096 ms |
3072 KB |
Time limit exceeded |
| 6 |
Execution timed out |
4050 ms |
8184 KB |
Time limit exceeded |
| 7 |
Execution timed out |
4086 ms |
3328 KB |
Time limit exceeded |
| 8 |
Execution timed out |
4077 ms |
2824 KB |
Time limit exceeded |
| 9 |
Execution timed out |
4059 ms |
3072 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
3960 KB |
Output is correct |
| 2 |
Correct |
66 ms |
4728 KB |
Output is correct |
| 3 |
Correct |
165 ms |
28408 KB |
Output is correct |
| 4 |
Correct |
338 ms |
30712 KB |
Output is correct |
| 5 |
Correct |
274 ms |
28536 KB |
Output is correct |
| 6 |
Execution timed out |
4081 ms |
2944 KB |
Time limit exceeded |
| 7 |
Execution timed out |
4066 ms |
44932 KB |
Time limit exceeded |
| 8 |
Execution timed out |
4058 ms |
22520 KB |
Time limit exceeded |
| 9 |
Execution timed out |
4062 ms |
8952 KB |
Time limit exceeded |
| 10 |
Execution timed out |
4070 ms |
3072 KB |
Time limit exceeded |
| 11 |
Execution timed out |
4067 ms |
6008 KB |
Time limit exceeded |
| 12 |
Execution timed out |
4096 ms |
2816 KB |
Time limit exceeded |
| 13 |
Execution timed out |
4096 ms |
3072 KB |
Time limit exceeded |
| 14 |
Execution timed out |
4050 ms |
8184 KB |
Time limit exceeded |
| 15 |
Execution timed out |
4086 ms |
3328 KB |
Time limit exceeded |
| 16 |
Execution timed out |
4077 ms |
2824 KB |
Time limit exceeded |
| 17 |
Execution timed out |
4059 ms |
3072 KB |
Time limit exceeded |
| 18 |
Execution timed out |
4093 ms |
5888 KB |
Time limit exceeded |
| 19 |
Execution timed out |
4081 ms |
33144 KB |
Time limit exceeded |
| 20 |
Execution timed out |
4062 ms |
3076 KB |
Time limit exceeded |
| 21 |
Runtime error |
14 ms |
9216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 22 |
Execution timed out |
4075 ms |
2944 KB |
Time limit exceeded |
