#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)
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));
}
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) {
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 + 1 > 0) {
if (lev - mx2 - 1 >= 0) l = qu(1, lev - mx2 - 1, lev - 1);
else l = -1;
}
if (l > -1) add[i] = add[vert[l]] + 1;
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);
}
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;
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);
}
}
vector<int> find(int N, int M, vector<int> A, vector<int> B, vector<int> W) {
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;
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> cntl(N, 0), cntr(N, 0);
for (int i = 0; i < len; i++) {
if (le[i] > -1) cntl[i] = cntl[le[i]] + 1;
}
for (int i = len-1; i >= 0; i--) {
if (ri[i] < len) cntr[i] = cntr[ri[i]] + 1;
}
//cout<<"count:\n";
//for (int i = 0; i < len; i++) cout << i << ' ' << cntl[i] << ' ' << cntr[i] << endl;
int lm = len / 2 - 1, rm = (len + 1) / 2;
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;
else res[row[i]] = 0;
}
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;
else res[row[i]] = 0;
}
if (len & 1) res[row[len / 2]] = 0;
vector<int> vert(N), add(N, 0);
for (int i = 1; i < len - 1; i++) {
dfs3(row[i], -1, g, dep, 0, vert, add);
}
for (int i = 0; i < N; i++) {
if (res[i] == -1) res[i] = res[row[par[i]]] + add[i];
}
/*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;*/
return res;
}
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 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
3796 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
210 ms |
18256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
326 ms |
24544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
3796 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
