还有4天就N01P了,估计我是最后一个写完这道题的了......
大佬都一眼切掉了这道题,我两个小时打了80分的暴力......
相关题目:「NOIP2016」天天爱跑步

小 C 同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。

这个游戏的地图可以看作一棵包含 n n 个结点和 n1 n - 1 条边的树,每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 1 1 n n 的连续正整数。

现在有 m m 个玩家,第 i i 个玩家的起点为 Si S_i ,终点为 Ti T_i 。每天打卡任务开始时,所有玩家在第 0 0 秒同时从自己的起点出发,以每秒跑一条边的速度,不间断地沿着最短路径向着自己的终点跑去,跑到终点后该玩家就算完成了打卡任务。(由于地图是一棵树,所以每个人的路径是唯一的)

小 C 想知道游戏的活跃度,所以在每个结点上都放置了一个观察员。在结点 j j 的观察员会选择在第 Wj W_j 秒观察玩家,一个玩家能被这个观察员观察到当且仅当该玩家在第 Wj W_j 秒也正好到达了结点 j j 。小 C 想知道每个观察员会观察到多少人?

注意:我们认为一个玩家到达自己的终点后该玩家就会结束游戏,他不能等待一段时间后再被观察员观察到。即对于把结点 j j 作为终点的玩家:若他在第 Wj W_j 秒前到达终点,则在结点 j j 的观察员不能观察到该玩家;若他正好在第 Wj W_j 秒到达终点,则在结点 j j 的观察员可以观察到这个玩家。

输入格式

第一行有两个整数 n n m m 。其中 n n 代表树的结点数量,同时也是观察员的数量,m m 代表玩家的数量。

接下来 n1 n - 1 行每行两个整数 u u v v ,表示结点 u u 到结点 v v 有一条边。

接下来一行 n n 个整数,其中第 i i 个整数为 Wi W_i ,表示结点 i i 出现观察员的时间。

接下来 m m 行,每行两个整数 Si S_i Ti T_i ,表示一个玩家的起点和终点。

对于所有的数据,保证 1Si,Tin,0Wjn 1 \leq S_i, T_i \leq n, 0 \leq W_j \leq n

输出格式

输出一行 n n 个整数,第 j j 个整数表示结点 j j 的观察员可以观察到多少人。

样例输入 1

6 3
2 3
1 2
1 4
4 5
4 6
0 2 5 1 2 3
1 5
1 3
2 6

样例输出 1

2 0 0 1 1 1

样例解释 1

对于 1 1 号点,W1=0 W_1 = 0 ,故只有起点为 1 1 号点的玩家才会被观察到,所以玩家 1 和玩家 2 被观察到,共 2 2 人被观察到。
对于 2 2 号点,没有玩家在第 2 2 秒时在此结点,共 0 0 人被观察到。
对于 3 3 号点,没有玩家在第 5 5 秒时在此结点,共 0 0 人被观察到。
对于 4 4 号点,玩家 1 1 被观察到,共 1 1 人被观察到。
对于 5 5 号点,玩家 2 2 被观察到,共 1 1 人被观察到。
对于 6 6 号点,玩家 3 3 被观察到,共 1 1 人被观察到。

样例输入 2

5 3
1 2
2 3
2 4
1 5
0 1 0 3 0
3 1
1 4
5 5

样例输出 2

1 2 1 0 1

数据范围

测试点 12 1 \sim 2 n=m=991 n = m = 991 ,所有人的起点等于自己的终点,即 Si=Ti S_i = T_i
测试点 34 3 \sim 4 n=m=992 n = m = 992 Wj=0 W_j = 0
测试点 5 5 n=m=993 n = m = 993
测试点 68 6 \sim 8 n=m=99994 n = m = 99994 ,树退化成一条链,对于 1i<n 1 \leq i < n i i i+1 i + 1 有边;
测试点 912 9 \sim 12 n=m=99995 n = m = 99995 Si=1 S_i = 1
测试点 1316 13 \sim 16 n=m=99996 n = m = 99996 Ti=1 T_i = 1
测试点 1719 17 \sim 19 n=m=99997 n = m = 99997
测试点 20 20 n=m=299998 n = m = 299998

Solution

25pts

枚举每个点,记录下时间跑一遍图,如果时间==wiw_{i}那么这个点对ii产生1的贡献。

40pts

结合以上,对于树退化成一条链的情况,对每个点ii产生贡献的点的起点为 ,只需判断一下路径是否越过 ii 即可。

60pts

结合以上,当 Si=1S_i=1 时,以 11 为根,对于点 ii ,能观察到人的点必须 WiW_i 与其深度相等,然后只要统计一下一个树的子树内有多少个点就好了。

80pts

结合以上,当 Ti=1T_i=1 时,以 11 为根,对于点 ii,会对他产生贡献的点的起点为 ii 的子树内距 ii 深度为 WiW_i 的点。可以考虑线段树合并,但有更简单的做法。考虑向下DFS ,对于点 ii ,答案就为搜索后子树内深度为 dep[i]+Widep[i]+W_i 的节点数与未搜索子树前的节点数之差。开个桶记录一下就好了。

100pts

80pts 的做法类似,将一条路径拆分为 向上 和 向下 两条链。对于向上的链,与之前相同,只需要在 lcalca 上打个 -1 的tag,在 ss 上打个1的tag,回溯的时候统计答案即可。

对于向下的链,以 tt 为对象,会产生贡献的人必须满足 dep[t]dep[i]=lenWidep[t]-dep[i]=len-W_i ,其中 lenlen 表示这个人的走的 路径长度。将有关 ii 的移到一边,于是可以开桶维护 dep[i]Widep[i]-W_i ,同样在两端分别打上tag就好了。(注意值域)

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
128
129
130
131
132
133
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
const int N = 300005;
int n, m;
int cnt,nxt[2*N],h[N],to[2*N];
inline void add(int u,int v) {nxt[++cnt]=h[u],to[h[u]=cnt]=v;}
int s[N], t[N], f[N][19], dep[N];
int ans[N], w[N];
void dfs(int u,int fa=0) {
*f[u]=fa;
for(int i=h[u];i;i=nxt[i])if(to[i]!=fa)dep[to[i]]=dep[u]+1,dfs(to[i],u);
}
int lca(int x,int y) {
if(dep[x]<dep[y]) swap(x,y);
for(int z=18;~z;--z)if(dep[f[x][z]]>=dep[y]) x=f[x][z];
if(x==y) return x;
for(int z=18;~z;--z)if(f[x][z]!=f[y][z]) x=f[x][z], y=f[y][z];
return *f[x];
}

namespace solve1 {
void sol() {
dep[1]=1; dfs(1);
rep(i,1,18)rep(x,1,n) f[x][i]=f[f[x][i-1]][i-1];
rep(i,1,m) {
int tim=0, u=s[i], v=t[i], p=lca(u,v);
for(;dep[u]>=dep[p];++tim,u=*f[u])if(w[u]==tim) ++ans[u];
tim=dep[s[i]]+dep[t[i]]-2*dep[p];
for(;dep[v]>dep[p];--tim,v=*f[v])if(w[v]==tim) ++ans[v];
}
rep(i,1,n) printf("%d ", ans[i]);
}
};
namespace solve2 {
vector<int> num[N];
void sol() {
rep(i,1,m) num[s[i]].push_back(t[i]);
rep(i,1,n) {
int u = i-w[i];
if(u>0) {for(unsigned z=0;z<num[u].size();++z)if(num[u][z]>=i)++ans[i];}
u = i+w[i];
if(u<=n){for(unsigned z=0;z<num[u].size();++z)if(num[u][z]<=i)++ans[i];}
if(w[i]==0) {for(unsigned z=0;z<num[z].size();++z)if(num[u][z]==i)--ans[i];}
}
rep(i,1,n) printf("%d ", ans[i]);
}
}
int val[N];
namespace solve3 {
int DFS(int u,int fa=0) {
for(int i=h[u];i;i=nxt[i])if(to[i]!=fa)
val[u] += DFS(to[i],u);
return val[u];
}
void sol() {
dep[1]=1; dfs(1);
rep(i,1,m) ++val[t[i]];
DFS(1);
rep(i,1,n)if(w[i]==dep[i]-1) {ans[i]=val[i];}
rep(i,1,n) printf("%d ", ans[i]);
}
}
namespace solve4 {
int b[N];
void DDFS(int u,int fa=0) {
int now=b[dep[u]+w[u]];
b[dep[u]]+=val[u];
for(int i=h[u];i;i=nxt[i])if(to[i]!=fa)dep[to[i]]=dep[u]+1,DDFS(to[i],u);
ans[u]=b[dep[u]+w[u]]-now;
}
void sol() {
rep(i,1,m) ++val[s[i]];
dep[1]=1; DDFS(1);
rep(i,1,n) printf("%d ", ans[i]);
}
}

namespace solve5 {
int b[N], tmp[N<<1], *c=tmp+N, len[N], p[N];
vector<int> v[N], v2[N], v3[N];
void DFS(int u,int fa=0) {
int deep=dep[u]+w[u], now;
if(deep<N) now=b[deep];
b[dep[u]]+=val[u];
for(int i=h[u];i;i=nxt[i])if(to[i]!=fa)DFS(to[i],u);
if(deep<N) ans[u]=b[deep]-now;
for(unsigned i=0;i<v[u].size();++i) --b[v[u][i]];
}
void DDFS(int u,int fa=0) {
int now=c[dep[u]-w[u]];
for(int i=h[u];i;i=nxt[i])if(to[i]!=fa)DDFS(to[i],u);
for(unsigned i=0;i<v2[u].size();++i) ++c[v2[u][i]];
ans[u]+=c[dep[u]-w[u]]-now;
for(unsigned i=0;i<v3[u].size();++i) --c[v3[u][i]];
}
inline void sol() {
dep[1]=1; dfs(1);
rep(i,1,18)rep(x,1,n) f[x][i]=f[f[x][i-1]][i-1];
rep(i,1,m) {
p[i]=lca(s[i],t[i]);
val[s[i]]++;
len[i]=dep[s[i]]+dep[t[i]]-2*dep[p[i]];
v[p[i]].push_back(dep[s[i]]);
}
DFS(1);
rep(i,1,m) {
v2[t[i]].push_back(dep[t[i]]-len[i]);
v3[p[i]].push_back(dep[t[i]]-len[i]);
}
DDFS(1);
rep(i,1,m)if(w[p[i]]==dep[s[i]]-dep[p[i]]&&dep[t[i]]-len[i]==dep[p[i]]-w[p[i]]) --ans[p[i]];
rep(i,1,n)printf("%d ", ans[i]);
}
}

int main() {
scanf("%d%d", &n, &m);
int u, v;
rep(i,2,n) {
scanf("%d%d", &u, &v);
add(u,v), add(v,u);
}
rep(i,1,n) scanf("%d", w+i);
rep(i,1,m) scanf("%d%d", s+i, t+i);
if(n<=1000) solve1::sol();
else if(n%10==4) solve2::sol();
else if(n%10==5) solve3::sol();
else if(n%10==6) solve4::sol();
else solve5::sol();
return 0;
}