找到问题了
> 数组开小
丢人...
AC 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int read() {
int ans = 0 , flag = 1;
char ch = getchar();
while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
return ans * flag;
}
const int N = 300000;
struct edge {int t , n;}e[N << 1];
int head[N] , tot;
void addedge(int u , int v) {
++ tot;
e[tot].t = v;
e[tot].n = head[u];
head[u] = tot;
}
int dep[N];
int w[N];
int n , m;
struct BZ {
int fa[N][20];
void prepare() {
for(int j = 1 ; j < 20 ; ++ j)
for(int i = 1 ; i <= n ; ++ i)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int lca(int a , int b) {
if(dep[a] < dep[b]) swap(a , b);
for(int i = 19 ; i >= 0 ; -- i)
if(dep[fa[a][i]] >= dep[b])
a = fa[a][i];
if(a == b) return a;
for(int i = 19 ; i >= 0 ; -- i)
if(fa[a][i] != fa[b][i]) {
a = fa[a][i];
b = fa[b][i];
}
return fa[a][0];
}
}Jump;
void dfs(int x , int f) {
Jump.fa[x][0] = f;
dep[x] = dep[f] + 1;
for(int i = head[x] ; i ; i = e[i].n) {
if(e[i].t == f) continue;
dfs(e[i].t , x);
}
}
vector <int> up[N] , down[N];
vector <int> del_up[N] , del_down[N];
int ins_up[N << 1] , ins_down[N << 1];
int ans[N];
void DFS(int x , int f) {
ans[x] -= ins_up[w[x] + dep[x]];
ans[x] -= ins_down[w[x] - dep[x] + n];
auto begin = up[x].begin() , end = up[x].end();
for(auto i = begin ; i != end ; ++ i) ++ ins_up[*i];
begin = down[x].begin(); end = down[x].end();
for(auto i = begin ; i != end ; ++ i) ++ ins_down[*i];
for(int i = head[x] ; i ; i = e[i].n) {
if(e[i].t == f) continue;
DFS(e[i].t , x);
}
ans[x] += ins_up[w[x] + dep[x]];
ans[x] += ins_down[w[x] - dep[x] + n];
begin = del_up[x].begin() , end = del_up[x].end();
for(auto i = begin ; i != end ; ++ i) -- ins_up[*i];
begin = del_down[x].begin(); end = del_down[x].end();
for(auto i = begin ; i != end ; ++ i) -- ins_down[*i];
}
int main() {
freopen("work.in" , "r" , stdin);
n = read(); m = read();
for(int i = 1 ; i < n ; ++ i) {
int x = read() , y = read();
addedge(x , y);
addedge(y , x);
}
dfs(1 , 0);
Jump.prepare();
for(int i = 1 ; i <= n ; ++ i) w[i] = read();
for(int i = 1 ; i <= m ; ++ i) {
int x = read() , y = read();
int lca = Jump.lca(x , y);
up[x].push_back(dep[x]);
del_up[lca].push_back(dep[x]);
down[y].push_back(dep[x] - 2 * dep[lca] + n);
del_down[lca].push_back(dep[x] - 2 * dep[lca] + n);
if(dep[x] - dep[lca] == w[lca]) -- ans[lca];
}
DFS(1 , 0);
for(int i = 1 ; i <= n ; ++ i) printf("%d " , ans[i]);
return 0;
}
```
by League丶翎 @ 2018-10-16 12:08:14
orz
by Fraction @ 2018-10-16 12:16:53
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈~~可以抄了~~
by Eason_AC @ 2018-10-16 12:49:52
不要加"的说"这类东西啊……汉语又不是黏着语听起来挺别扭的……
by shadowice1984 @ 2018-10-16 14:34:29