#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)
#define btinpct(x) __builtin_popcountll((x))
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 to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){if(a>b)swap(a,b);if(a==0)return b;return gcd(b%a,a);}
#define ll /*long long*/ int
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (200006)
ll n, m;
vector<int> v[MAXN];
int A[MAXN], p[MAXN];
bool F[MAXN];
ll fdist[MAXN], depth[MAXN], rdist[MAXN];
void init(ll x,ll par) {
rdist[x] = fdist[x] = depth[x]; p[x]=par;
pi mx=pi(depth[x], 1);
pi fmx=pi(depth[x], 1);
for(auto i:v[x]) if(i^par) {
depth[i]=depth[x]+1; init(i, x);
rdist[x]=max(rdist[x], rdist[i]);
if(rdist[i] > mx.f) mx.f=rdist[i], mx.s=1;
else if(rdist[i] == mx.f) ++ mx.s;
// fmx=max(fmx, fdist[i]);
if(fdist[i] > fmx.f) fmx.f=fdist[i], fmx.s=1;
else if(fdist[i] == fmx.f) ++ fmx.s;
}
ll rmx=-1;
for(auto i:v[x]) if(i^par) {
if(fdist[i] ^ fmx.f) rmx=max(rmx, rdist[i]);
}
if(mx.s == 1 && fmx.f > rmx && fmx.s==1) fdist[x]=fmx.f;
}
ll ans[MAXN];
bool can(set<pi,greater<pi>> s) {
if(s.empty()) return 1;
ll x = s.begin()->f;
ll times=1;
s.erase(s.begin());
for(auto i:s) {
if(i.f == x) ++ times;
}
return times==1;
}
void dfs(ll x,ll par,ll dist,ll rup) {
pi mx = pi(dist , 1);
ll rmx=0;
for(auto i:v[x]) if(i^par) {
fdist[i] -= depth[x];
if(fdist[i] > mx.f) mx.f = fdist[i], mx.s=1;
else if(fdist[i] == mx.f) ++ mx.s;
fdist[i] += depth[x];
rmx=max(rmx, rdist[i]-depth[x]);
}
if(mx.f != dist) rmx=rup; else rmx=0;
for(auto i:v[x]) if(i^par) if(mx.f != fdist[i]-depth[x]) rmx=max(rmx, rdist[i]-depth[x]);
// if(x==3) cerr<<mx.f<<' '<<mx.s<<' '<<rmx<<' '<<dist<<' '<<rup<<"\n";
if(mx.s == 1 && mx.f > rmx) {
ans[x] = 1;
}
set<pi,greater<pi>> ms;
multiset<ll,greater<ll>> R;
ms.ins(pi(dist, x)); R.ins(rup);
for(auto i:v[x]) if(i^par) {
ms.ins(pi(fdist[i]-depth[x], i));
R.ins(rdist[i]-depth[x]);
}
// while(ms.size() > 4) ms.erase(--ms.end());
// while(R.size() > 4) R.erase(--R.end());
ll o=ms.size(); ll oR=R.size();
for(auto i:v[x])if(i^par){
ms.erase(pi(fdist[i]-depth[x], i));
if(ms.begin()->s != x) R.erase(R.find(rdist[ms.begin()->s]-depth[x])); else R.erase(R.find(rup));
if(*R.begin() == rdist[i]-depth[x]) R.erase(R.begin());
if((ms.size() >= 2 && ms.begin()->f == next(ms.begin())->f) || (R.size()&&ms.begin()->f <= *R.begin())) {
if(ms.begin()->s != x) R.ins(rdist[ms.begin()->s]-depth[x]);
else R.ins(rup);
dfs(i, x, 1, *R.begin() + 1);
} else {
if(ms.begin()->s != x) R.ins(rdist[ms.begin()->s]-depth[x]);
else R.ins(rup);
dfs(i, x, (ms.begin()->f) + 1, *R.begin() + 1);
}
if(siz(ms) ^ o) ms.ins(pi(fdist[i]-depth[x],i));
if(siz(R) ^ oR) R.ins(rdist[i]-depth[x]);
}
}
void comp(ll i) {
for(auto j:v[i]) if(j^p[i]) comp(j);
pi ans=pi(0, 1);
bool gg=0;
for(auto j:v[i]) if(j^p[i]) { gg |= (!F[j]);
if(fdist[j] > ans.f) ans.f=fdist[j], ans.s=1;
else if(fdist[j]==ans.f) ++ ans.s;
}
F[i] = (ans.s == 1);
if(gg) F[i]=0;
}
int main()
{
FAST
cin>>n>>m;
FOR(i,0,n-2) {
ll a, b; cin>>a>>b;
v[a].eb(b), v[b].eb(a);
}
FOR(i,1,n) cin>>A[i];
init(1, 1);
// comp(1);
FOR(i,1,n) {
// cerr<<i<<": "<<fdist[i]<<"\n";
}
dfs(1, 1, 0, 0);
FOR(i,1,n) cout<<ans[i]<<"\n";
}
/*
10 10
2 6
5 8
10 8
1 4
10 6
4 5
10 7
6 9
3 7
1 2 3 4 5 6 7 8 9 10
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
5240 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
285 ms |
13308 KB |
Output is correct |
| 2 |
Correct |
269 ms |
43472 KB |
Output is correct |
| 3 |
Correct |
50 ms |
10616 KB |
Output is correct |
| 4 |
Correct |
394 ms |
19644 KB |
Output is correct |
| 5 |
Correct |
580 ms |
53524 KB |
Output is correct |
| 6 |
Correct |
479 ms |
48376 KB |
Output is correct |
| 7 |
Correct |
499 ms |
23024 KB |
Output is correct |
| 8 |
Correct |
436 ms |
26052 KB |
Output is correct |
| 9 |
Correct |
418 ms |
25484 KB |
Output is correct |
| 10 |
Correct |
434 ms |
25808 KB |
Output is correct |
| 11 |
Correct |
1000 ms |
37700 KB |
Output is correct |
| 12 |
Correct |
477 ms |
65144 KB |
Output is correct |
| 13 |
Correct |
611 ms |
43344 KB |
Output is correct |
| 14 |
Correct |
508 ms |
47220 KB |
Output is correct |
| 15 |
Correct |
973 ms |
38872 KB |
Output is correct |
| 16 |
Correct |
612 ms |
47860 KB |
Output is correct |
| 17 |
Correct |
525 ms |
45824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
320 ms |
17156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
5240 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
