#include<iostream>
#include<vector>
using namespace std;
#include<iostream>
#include<vector>
#include<set>
#include<stack>
using namespace std;
#define pi pair<int,int>
#define x first
#define y second
#define maxn (1<<17)
#define maxs (1<<18)
#define maxm 50000000
vector<int> v(2 * maxn, 1e9), l(2 * maxn), r(2 * maxn);
void bld() {
for (int i = maxn; i < 2 * maxn; i++) {
l[i] = r[i] = i - maxn;
}
for (int i = maxn - 1; i > 0; i--) {
l[i] = l[2 * i];
r[i] = r[2 * i + 1];
}
}
void up(int i, int u) {
i += maxn;
v[i] = u;
while (i >>= 1) v[i] = min(v[i << 1], v[(i << 1) + 1]);
}
int qu(int i, int s, int e) {
if (l[i] > e || r[i] < s) return 1e9;
if (l[i] >= s && r[i] <= e) return v[i];
return min(qu(i << 1, s, e), qu((i << 1) + 1, s, e));
}
int nxt = 0;
vector<int> vp(maxm,0), lp(maxm,-1), rp(maxm,-1);
void upp(int ind, int i, int l, int r) {
int u = nxt; nxt++;
if (ind != -1) vp[u] = vp[ind] + 1;
else vp[u] = 1;
//cout << ind << ' ' << u << ' ' << vp[u] << endl;
if (l == r) return;
int rs = ind == -1 ? -1 : rp[ind], ls = ind == -1 ? -1 : lp[ind];
int m = (l + r) / 2;
if (i > m) {
upp(rs, i, m + 1, r);
rp[u] = u + 1;
lp[u] = ls;
}
else {
upp(ls, i, l, m);
lp[u] = u + 1;
rp[u] = rs;
}
}
int check(int ind, int i, int l, int r) {
if (ind == -1) return 0;
if (l == r) return vp[ind];
int m = (l + r) / 2;
if (i > m) return check(rp[ind], i, m + 1, r);
else return check(lp[ind], i, l, m);
}
int sm(int ind) {
if (ind == -1) return 0;
return vp[ind];
}
pi dfs0(int i, int p, vector<vector<int>>& g) {
pi pr = { 0,i };
for (int j : g[i]) {
if (j == p) continue;
pi r = dfs0(j, i, g);
r.x++;
if (r > pr) pr = r;
}
return pr;
}
bool dfs1(int i, int p, vector<vector<int>>& g, int d, vector<int>&dep, vector<int>&row, int x) {
bool flag = 0;
if (i == x) flag = 1;
dep[i] = 0;
for (int j : g[i]) {
if (j == p) continue;
if (dfs1(j, i, g, d + 1, dep, row, x)) flag = 1;
else dep[i] = max(dep[i], dep[j] + 1);
}
if (flag) row[d] = i;
return flag;
}
void dfs2(int i, int p, vector<vector<int>>& g, vector<int>&par, int f) {
par[i] = f;
for (int j : g[i]) {
if (j == p) continue;
dfs2(j, i, g, par, f);
}
}
void dfs3(int i, int p, vector<vector<int>>& g, vector<int>&dep, int lev, vector<int> &vert, vector<int>&add, vector<int>&indres, vector<int>&W) {
int mx1 = -1, mx2 =-1;
for (int j : g[i]) {
if (j == p) continue;
if (dep[j]+1 > mx1) {
mx2 = mx1;
mx1 = dep[j]+1;
}
else if (dep[j]+1 > mx2) mx2 = dep[j]+1;
}
vert[lev] = i;
int l = lev - 1;
if (mx2 > 0) {
if (lev - mx2 >= 0) l = qu(1, lev - mx2, lev - 1);
else l = -1;
}
if (l > -1) {
//add[i] = add[vert[l]] + 1;
if (check(indres[vert[l]], W[vert[l]], 0, maxs - 1)) {
indres[i] = indres[vert[l]];
}
else {
indres[i] = nxt;
upp(indres[vert[l]], W[vert[l]], 0, maxs - 1);
}
}
else indres[i] = indres[vert[0]];
//else add[i] = 0;
up(lev, l);
for (int j : g[i]) {
if (j == p) continue;
if (dep[j] + 1 == mx1) dfs3(j, i, g, dep, lev + 1, vert, add, indres,W);
}
l = lev - 1;
if (dep[i] > 0) {
if (lev - dep[i] >= 0) l = qu(1, lev - dep[i], lev - 1);
else l = -1;
}
if (l > -1) {
//add[i] = add[vert[l]] + 1;
if (check(indres[vert[l]], W[vert[l]], 0, maxs - 1)) {
indres[i] = indres[vert[l]];
}
else {
indres[i] = nxt;
upp(indres[vert[l]], W[vert[l]], 0, maxs - 1);
}
}
else indres[i] = indres[vert[0]];
//else add[i] = 0;
up(lev, l);
for (int j : g[i]) {
if (j == p) continue;
if (dep[j] + 1 == mx1) continue;
dfs3(j, i, g, dep, lev + 1, vert, add, indres,W);
}
}
void dfs(int i, int p, int d, vector<vector<int>>& vec, vector<vector<int>>& g) {
vec[d].push_back(i);
for (int j : g[i]) {
if (j != p) dfs(j, i, d + 1, vec, g);
}
}
vector<int> find(int N, int M, vector<int> A, vector<int> B, vector<int> W) {
if (N <= 3) {
vector<int> res(N, -1);
vector<vector<int>> g(N);
for (int i = 0; i < N - 1; i++) {
g[A[i] - 1].push_back(B[i] - 1);
g[B[i] - 1].push_back(A[i] - 1);
}
for (int i = 0; i < N; i++) {
vector<vector<int>> vec(N);
dfs(i, -1, 0, vec, g);
set<int> st;
for (int j = 1; j < N; j++) if (vec[j].size() == 1) st.insert(W[vec[j][0]]);
res[i] = st.size();
}
return res;
}
bld();
vector<int> res(N, -1);
vector<vector<int>> g(N);
for (int i = 0; i < N - 1; i++) {
g[A[i] - 1].push_back(B[i] - 1);
g[B[i] - 1].push_back(A[i] - 1);
}
int rt = dfs0(0, -1, g).y;
pi pr = dfs0(rt, -1, g);
int ort = pr.y, len = pr.x + 1;
vector<int> dep(N, 0), row(len, -1);
dfs1(rt, -1, g, 0, dep, row, ort);
//for (int i : dep) cout << i << ' '; cout << endl;
//for (int i : row) cout << i << ' '; cout << endl;
//for (int i : row) cout << dep[i] << ' '; cout << endl;
vector<int> par(N, -1);
for (int i = 1; i < len - 1; i++) {
for (int& j : g[row[i]]) if (j == row[i - 1] || j == row[i + 1]) j = -1;
dfs2(row[i], -1, g, par, i);
}
//for (int i : par) cout << i << ' '; cout << endl;
vector<int> le(len, -1), ri(len, len);
stack<int> sk;
//monotonic stack
for (int i = 0; i < len; i++) {
int u = row[i];
int to = i - dep[u];
while (sk.size() && to <= sk.top()) {
if (le[sk.top()]+1 < to) to = le[sk.top()]+1;
sk.pop();
}
le[i] = (to >= 0) ? to - 1 : -1;
sk.push(i);
}
for (int i = len - 1; i >= 0; i--) {
int u = row[i];
int to = i + dep[u];
while (sk.size() && to >= sk.top()) {
if (ri[sk.top()]-1 > to) to = ri[sk.top()]-1;
sk.pop();
}
ri[i] = to < len ? to + 1 : len;
sk.push(i);
}
//for (int i = 0; i < len; i++) cout << i << ' ' << le[i] << ' ' << ri[i] << endl;
vector<int> indl(len, -1), indr(len, -1);
//vector<int> cntl(N, 0), cntr(N, 0);
for (int i = 0; i < len; i++) {
if (le[i] > -1) {
//cntl[i] = cntl[le[i]] + 1;
if (check(indl[le[i]], W[row[le[i]]], 0, maxs - 1)) {
indl[i] = indl[le[i]];
}
else {
indl[i] = nxt;
upp(indl[le[i]], W[row[le[i]]], 0, maxs - 1);
}
}
}
for (int i = len-1; i >= 0; i--) {
//if (ri[i] < len) cntr[i] = cntr[ri[i]] + 1;
if (ri[i] >= len) continue;
if (check(indr[ri[i]], W[row[ri[i]]], 0, maxs - 1)) {
indr[i] = indr[ri[i]];
}
else {
indr[i] = nxt;
upp(indr[ri[i]], W[row[ri[i]]], 0, maxs - 1);
}
}
//cout<<"count:\n";
//for (int i = 0; i < len; i++) cout << i << ' ' << cntl[i] << ' ' << cntr[i] << endl;
//for (int i : indr) cout << i << ' '; cout << endl;
//for (int i : indl) cout << i << ' '; cout << endl;
int lm = len / 2 - 1, rm = (len + 1) / 2;
vector<int> indres(N, -1);
vector<int> rcl(N, 0), rcr(N, 0);
int rto = -1, cto = -1;
for (int i = 0; i <= lm; i++) {
cto = max(cto, 2 * i + 1);
while (rto < cto - 1) {
rto++;
if (rto + dep[row[rto]] + 1 > cto) cto = rto + dep[row[rto]] + 1;
if (cto > len) cto = len;
}
if (cto < len) {
//res[row[i]] = cntr[cto] + 1;
if (check(indr[cto], W[row[cto]], 0, maxs - 1)) {
//cout << i << 'A';
indres[row[i]] = indr[cto];
}
else {
//cout << i << 'B';
indres[row[i]] = nxt;
upp(indr[cto], W[row[cto]], 0, maxs - 1);
}
}
//else res[row[i]] = 0;
}//cout << endl;
int lto = len;
cto = len;
for (int i = len-1; i >= rm; i--) {
cto = min(cto, 2*i - len);
while (lto > cto + 1) {
lto--;
if (lto - dep[row[lto]] - 1 < cto) cto = lto - dep[row[lto]] - 1;
if (cto < 0) cto = -1;
}
if (cto >= 0) {
//res[row[i]] = cntl[cto] + 1;
if (check(indl[cto], W[row[cto]], 0, maxs - 1)) {
indres[row[i]] = indl[cto];
}
else {
indres[row[i]] = nxt;
upp(indl[cto], W[row[cto]], 0, maxs - 1);
}
}
//else res[row[i]] = 0;
}
//if (len & 1) res[row[len / 2]] = 0;
//for (int i : row) cout << i << ' ' << indres[i] << endl;
vector<int> vert(N), add(N, 0);
for (int i = 1; i < len - 1; i++) {
dfs3(row[i], -1, g, dep, 0, vert, add, indres,W);
}
for (int i = 0; i < N; i++) {
//if (res[i] == -1) res[i] = res[row[par[i]]] + add[i];
res[i] = sm(indres[i]);
}
//persistent seg tree for 100!
/*vector<int> am(len), ap(len);
vector<vector<int>> vp(18, vector<int>(len, 1e9)), vm(18, vector<int>(len, 1e9));
for (int i = 0; i < len; i++) {
am[i] = i - dep[i];
ap[i] = i + dep[i];
vm[0][i] = am[i];
vp[0][i] = ap[i];
}
for (int j = 1; j < 18; j++) {
for (int i = 0; i < len; i++) {
vp[j][i] = vp[j - 1][i];
vm[j][i] = vm[j - 1][i];
}
for (int i = 0; i + (1 << (j - 1)) < len; i++) {
vp[j][i] = min(vp[j - 1][i], vp[j - 1][i + (1 << (j - 1))]);
vm[j][i] = min(vm[j - 1][i], vm[j - 1][i + (1 << (j - 1))]);
}
}
vector<int> lg(len+1, 0);
lg[1] = 0;
for (int i = 2; i <= len; i++) lg[i] = lg[i / 2] + 1;*/
//if (W[0] == W[1]) for (int &i : res) if (i > 1) i = 1;
return res;
}
/*
15 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
5 10
10 11
10 14
11 12
11 13
13 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
*/
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
vector<int> A(N - 1), B(N - 1);
for (int i = 0; i < N - 1; i++) {
cin >> A[i] >> B[i];
}
vector<int> W(N);
for (int i = 0; i < N; i++) {
cin >> W[i];
}
vector<int> ans = find(N, M, A, B, W);
for (int i = 0; i < N; i++) {
cout << ans[i] << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
94 ms |
274432 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
77 ms |
274432 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
80 ms |
274432 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
94 ms |
274432 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
