我不是导神 @ 2019-02-09 19:43:57
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#define N 300000
using namespace std;
int n, m, t, tot = 0;
int hd[N], nxt[N*2], ver[N*2];
int f[N][20], d[N], w[N], v[N], c1[N], c2[N];
int ans[N];
queue<int> q;
vector<int> a1[N], b1[N], a2[N], b2[N];
inline int rd() {
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') x = x*10 + ch - '0', ch = getchar();
return f*x;
}
void add(int x, int y) {
ver[++tot] = y, nxt[tot] = hd[x], hd[x] = tot;
}
void bfs() {
d[1] = 1, q.push(1);
while(q.size()) {
int x = q.front();
q.pop();
for(int i = hd[x]; i; i = nxt[i]) {
int y = ver[i];
if(d[y]) continue;
d[y] = d[x] + 1;
f[y][0] = x;
for(int j = 1; j <= t; j++) {
f[y][j] = f[f[y][j - 1]][j - 1];
}
q.push(y);
}
}
}
int lca(int x, int y) {
if(d[x] > d[y]) swap(x, y);
for(int i = t; i >= 0; i--) {
if(d[f[y][i]] >= d[x]) y = f[y][i];
}
if(x == y) return x;
for(int i = t; i >= 0; i--) {
if(f[y][i] != f[x][i]) x = f[x][i], y = f[y][i];
}
return f[x][0];
}
void dfs(int x) {
int val1 = c1[d[x] + w[x]], val2 = c2[w[x] - d[x] + n];
v[x] = 1;
for(int i = hd[x]; i; i = nxt[i]) {
int y = ver[i];
if(v[y]) continue;
dfs(y);
}
for(int i = 0; i < a1[x].size(); i++) c1[a1[x][i]]++;
for(int i = 0; i < b1[x].size(); i++) c1[b1[x][i]]--;
for(int i = 0; i < a2[x].size(); i++) c2[a2[x][i] + n]++;
for(int i = 0; i < b2[x].size(); i++) c2[b2[x][i] + n]--;
ans[x] += c1[d[x] + w[x]] - val1 + c2[w[x] - d[x] + n] - val2;
}
int main() {
// freopen("run.in","r",stdin);
// freopen("run.out","w",stdout);
n = rd(), m = rd();
t = (int)(log(n) / log(2)) + 1;
for(int i = 1; i < n; i++) {
int x = rd(), y = rd();
add(x, y), add(y, x);
}
for(int i = 1; i <= n; i++) w[i] = rd();
bfs();
for(int i = 1; i <= m; i++) {
int x = rd(), y = rd();
int z = lca(x, y);
a1[x].push_back(d[x]);
b1[f[z][0]].push_back(d[x]);
a2[y].push_back(d[x] - 2 * d[z]);
b2[z].push_back(d[x] - 2 * d[z]);
}
dfs(1);
for(int i = 1; i < n; i++) printf("%d ", ans[i]);
printf("%d\n", ans[n]);
return 0;
}
by ZQYZQY @ 2019-10-17 11:12:41
+1
by ZQYZQY @ 2019-10-17 11:13:09
@我不是导神 大佬有查出吗?