天天爱跑步

发表于 分类于

Problem’s Website

天天爱跑步

Solution

这道题的题意还是很好理解的。

做法好像有很多种，因为我是个 菜鸡 ，所以就说一种比较$low$的做法。

本题要用到的数据结构

  • 树链剖分

  • 动态开点线段树

以上两个内容在我的blog中都有相关内容，如果有不会的同学可以先去学习一下。

基本思路

我们将一个人的路线拆分一下，拆成$s \to LCA(s, t) \to t$，那么显然，当$dep[s]-dep[i]==w[i]$或$dep[t]-dep[i]==dis(s,t)-w[i]$时（$dis$为两点间的距离, 前面一个式子用于第一段，后面的式子用于第二段 ），答案可以$+1$，其实我们可以差分来做，但我是 菜鸡，我不会那么做，所以“智商不够，数据结构来凑！”，我们用一个动态开点线段树来维护。

特别注意：对于$LCA$要判重！

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc getchar()
#define pc(x) putchar(x)
#define re register
const int Maxn = 3e5 + 10;
inline int sc() {
    int xx = 0, ff = 1; char cch = gc;
    while(!isdigit(cch)) {
        if(cch == '-') ff = -1; cch = gc;
    }
    while(isdigit(cch)) {
        xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
    }
    return xx * ff;
}
inline void out(int x) {
    if(x < 0) pc('-'), x = -x;
    if(x >= 10) out(x / 10);
    pc(x % 10 + '0');
}
struct node{
	int next, to;
}Map[Maxn << 1];
int n, m, cnt;
int head[Maxn], w[Maxn], s[Maxn], t[Maxn], lca[Maxn], ans[Maxn];
int fa[Maxn], son[Maxn], siz[Maxn], top[Maxn], id[Maxn], dep[Maxn];
int rt[Maxn * 3], L[Maxn * 30], R[Maxn * 30], sum[Maxn * 30];
inline void ADD(int from, int to) {
	Map[++cnt].next = head[from];
	Map[cnt].to = to;
	head[from] = cnt;
}
inline void dfs1(int now, int Fa, int Dep) {
	fa[now] = Fa, dep[now] = Dep, siz[now] = 1;
	for(re int i = head[now]; i; i = Map[i].next) {
		int to = Map[i].to;
		if(to == Fa)
			continue;
		dfs1(to, now, Dep + 1);
		siz[now] += siz[to];
		if(siz[son[now]] < siz[to])
			son[now] = to;
	}
}
inline void dfs2(int now, int topf) {
	id[now] = ++cnt, top[now] = topf;
	if(!son[now])
		return;
	dfs2(son[now], topf);
	for(re int i = head[now]; i; i = Map[i].next) {
		int to = Map[i].to;
		if(to == fa[now] || to == son[now])
			continue;
		dfs2(to, to);
	}
}
inline int LCA(int x, int y) {
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]])
			std :: swap(x, y);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y])
		std :: swap(x, y);
	return x;
}
inline void modify(int &k, int l, int r, int x, int z) {
	if(!k)
		k = ++cnt, L[k] = R[k] = sum[k] = 0;
	sum[k] += z;
	if(l == r)
		return ;
	int mid = l + r >> 1;
	if(x <= mid) modify(L[k], l, mid, x, z);
	else modify(R[k], mid + 1, r, x, z);
}
inline int query(int k, int l, int r, int x, int y) {
	if(!k)
		return 0;
	if(x <= l && r <= y)
		return sum[k];
	int mid = l + r >> 1, res = 0;
	if(x <= mid) res += query(L[k], l, mid, x, y);
	if(y > mid) res += query(R[k], mid + 1, r, x, y);
	return res;
}
int main() {
	n = sc(), m = sc();
	for(re int i = 1; i < n; ++i) {
		int x = sc(), y = sc();
		ADD(x, y);
		ADD(y, x);
	}
	cnt = 0;
	dfs1(1, 0, 0), dfs2(1, 1);
	cnt = 0;
	for(re int i = 1; i <= n; ++i)
		w[i] = sc();
	for(re int i = 1; i <= m; ++i) {
		s[i] = sc(), t[i] = sc();
		lca[i] = LCA(s[i], t[i]);
		if(dep[s[i]] - dep[lca[i]] == w[lca[i]])
			--ans[lca[i]];
		modify(rt[dep[s[i]]], 1, n, id[s[i]], 1);
		if(fa[lca[i]])
			modify(rt[dep[s[i]]], 1, n, id[fa[lca[i]]], -1);
	}
	for(re int i = 1; i <= n; ++i)
		ans[i] += query(rt[dep[i] + w[i]], 1, n, id[i], id[i] + siz[i] - 1);
	cnt = 0;
	memset(rt, 0, sizeof(rt));
	for(re int i = 1; i <= m; ++i) {
		modify(rt[dep[s[i]] - (dep[lca[i]] << 1) + (n << 1)], 1, n, id[t[i]], 1);
		if(fa[lca[i]])
			modify(rt[dep[s[i]] - (dep[lca[i]] << 1) + (n << 1)], 1, n, id[fa[lca[i]]], -1);
	}
	for(re int i = 1; i <= n; ++i) {
		ans[i] += query(rt[w[i] - dep[i] + (n << 1)], 1, n, id[i], id[i] + siz[i] - 1);
		out(ans[i]), pc(' ');
	}
	pc('\n');
    return 0;
}
// Coded by dy.

rp++