https://www.luogu.org/problemnew/show/P1600

nlogn竟然T了

#include
#include
#include
#include
#include

using namespace std;
const int N = ;
const int oo = ;

#define lson jd << 1
#define rson jd << 1 | 1

#define yxy getchar()
#define one_ n <= 993
#define two_ n == 99994
#define three_ n == 99995

int head[N], pre[N], dis[N], tim[N], Answer[N], Askl[N], Askr[N];
bool vis[N];
int n, m, now = ;
struct Node {int u, v, w, nxt;}G[N];
queue Q;
vector Vt[N];
int bef[N], top[N], deep[N], size[N], fa[N], son[N], tree[N], spjs;
int L[N << ], R[N << ], W[N << ], F[N << ];
int ans;

inline int read() {
int x = ; char c = yxy;
while(c < '' || c > '') c = yxy;
while(c >= '' && c <= '') x = x * + c - '', c = yxy;
return x;
}

inline void add(int u, int v) {G[now].v = v;G[now].nxt = head[u]; head[u] = now ++;}

inline void spfa(int start,int endd) {
for(int i = ; i <= n; i ++) dis[i] = oo, vis[i] = ; dis[start] = ; Q.push(start); while(!Q.empty()) { int topp = Q.front(); Q.pop(); vis[topp] = ; for(int i = head[topp]; ~ i; i = G[i].nxt) { if(dis[G[i].v] > dis[topp] + ) {
dis[G[i].v] = dis[topp] + ;
pre[G[i].v] = topp;
if(!vis[G[i].v]) {vis[G[i].v] = ; Q.push(G[i].v);}
}
}
}
}

void calc(int start, int endd, int diss) {
int js = -; pre[start] = ;
while(endd) {
js ++;
if(tim[endd] == diss - js) Answer[endd] ++;
endd = pre[endd];
}
}

void work_1() {
for(int i = ; i <= m; i ++) {
spfa(Askl[i], Askr[i]);
calc(Askl[i], Askr[i], dis[Askr[i]]);
}
}

void work_2() {
for(int i = ; i <= m; i ++) Vt[Askl[i]].push_back(Askr[i]); for(int i = ; i <= n; i ++) { int L_ = i - tim[i], R_ = i + tim[i]; int siz_ = Vt[L_].size(); if(L_ > )
for(int j = ; j < siz_; j ++) if(Vt[L_][j] >= i) Answer[i] ++;
siz_ = Vt[R_].size();
if(R_ <= n)
for(int j = ; j < siz_; j ++)
if(Vt[R_][j] <= i) Answer[i] ++;
}
}

void Dfs_son(int u, int f_, int dep) {
printf("%d %d\n", u, f_);
fa[u] = f_;
deep[u] = dep;
size[u] = ;
for(int i = head[u]; ~ i; i = G[i].nxt) {
int v = G[i].v;
if(v != f_) {
Dfs_son(v, u, dep + );
if(size[v] > size[son[u]]) son[u] = v;
}
}
}

void Dfs_un(int u, int tp){
top[u] = tp;
tree[u] = ++ spjs;
bef[spjs] = u;
if(!son[u]) return ;
Dfs_un(son[u], tp);
for(int i = head[u]; ~ i; i = G[i].nxt) {
int v = G[i].v;
if(v != fa[u] && v != son[u]) Dfs_un(v, v);
}
}

void Sec_G(int l, int r, int jd, int x, int y) {
if(x <= l && r <= y) { F[jd] ++; W[jd] += (r - l + ); return ; } int mid = (l + r) >> ;
if(x <= mid) Sec_G(l, mid, lson, x, y); if(y > mid) Sec_G(mid + , r, rson, x, y);
W[jd] = W[lson] + W[rson];
}

void down(int jd) {
F[lson] += F[jd]; F[rson] += F[jd];
W[lson] += (R[lson] - L[lson] + ) * F[jd];
W[rson] += (R[rson] - L[rson] + ) * F[jd];
F[jd] = ;
}

inline void Sec_G_imp(int x, int y) {
int tp1 = deep[x], tp2 = deep[y];
while(tp1 != tp2) {
if(deep[tp1] < deep[tp2]) swap(x, y), swap(tp1, tp2);
Sec_G(, n, , tree[tp1], tree[x]);
x = fa[tp1];
tp1 = top[x];
}
if(deep[x] < deep[y]) swap(x, y);
Sec_G(, n, , tree[y], tree[x]);
return ;
}

void Dfs_calc(int l, int r, int jd) {
if(l == r) {
if(deep[bef[l]] == tim[bef[l]]) Answer[bef[l]] = W[jd];
return ;
}
if(F[jd]) down(jd);
int mid = (l + r) >> ;
Dfs_calc(l, mid, lson);
Dfs_calc(mid + , r, rson);
}

void work_3(){
Dfs_son(, , );
Dfs_un(, );
for(int i = ; i <= m; i ++) Sec_G_imp(Askl[i], Askr[i]);
Dfs_calc(, n, );
}

int main()
{
n = read(); m = read();
for(int i = ; i <= n; i ++) head[i] = -;
for(int i = ; i <= n - ; i ++) {int u = read(); int v = read(); add(u, v); add(v, u);}
for(int i = ; i <= n; i ++) tim[i] = read();
for(int i = ; i <= m; i ++) Askl[i] = read(), Askr[i] = read();
if(one_) work_1();
else if(two_) work_2();
else if(three_) work_3();
for(int i = ; i <= n; i ++) printf("%d ", Answer[i]);
return ;
}