数据分析
首先这道题可以暴力。
暴力+部分数据骗分可以拿到75分，相当不错的分数。
初步想法
暴力既然超时，那么这道题一定有更优的解法。
尝试写出能够观察到玩家的结点具有的性质：
将路径拆成通过$lca$的两条链
①对于左链（即从开始结点$u$走到$lca$）
其中$D[i]$代表$i$结点的深度，$x$是路径上的点。
移项得：
故能够观察到的结点满足以上性质。
看到这个式子，左边是定值右边是非定值有没有什么想法？
②让我们再看看右链（即从$lca$走到结束结点$v$）
其中$len$是路径长度，对于边权为1的树可以表示为：$D[u]+D[v]-2D[lca]$
那么原式化简为：
这个式子同样左边是定值右边是非定值。
是不是有什么想法了？
数据结构
如果我们使用一个数据结构在树上遍历时动态维护这些定值，同时遍历时处理掉式子右边的非定值，不就可以实现与玩家数目无关的离线快速计算了吗？
这个数据结构是什么呢？
没错就是树上的Hash表。
在处理玩家时，我们在开始结点$u$与结束结点$v$打上添加标记，在$lca$处打上删除标记，然后打完标记后开始遍历。
遍历的时候如果遇到一个结点有添加标记就在Hash表中将它加入，然后对于这个结点统计答案，如果遇到删除标记就把它删除。
具体的来讲，每一个结点维护以下信息：
- $LAdd[i][]$：$i$结点左链的添加数值
- $LDel[i][]$：$i$结点左链的删除数值
- $RAdd[i][]$：$i$结点右链的添加数值
- $RDel[i][]$：$i$结点右链的删除数值
对于整棵树，维护两个Hash表
- $Hash1[x]$：左链上数值为x的有多少个
- $Hash2[x]$：右链上数值为x的有多少个
再看看图：
那么我们对于每一个新的玩家，拆成两条链后。
在开始结点处在$LAdd[u][]$中添加新的数值$D[u]$
在结束结点处在$RAdd[u][]$中添加新的数值$D[u]-2D[lca]$
在$lca$处在$LDel[lca][]$中添加新的数值$D[u]$
在$lca$处在$RDel[lca][]$中添加新的数值$D[u]-2D[lca]$
注意特殊处理只有左链和只有右链的情况。
还要注意如果左链右链都存在时$lca$会重复统计，所以如果$lca$满足条件，给其答案$Ans[lca]-1$
最后我们处理完了所有玩家，开始对树进行Dfs后序遍历。
第一次遍历我们处理左链。
对于每一个结点$x$，后序处理以下信息：
若$LAdd[x][]$中有值，将其所有值加入Hash表：$Hash[LAdd[x,i]]++$
然后统计答案：
接着若$LDel[x][]$中有值，将其所有值从Hash表中删除：$Hash[LDel[x,i]]—$
那么这样信息就维护完了。
注意细节，因为树有很多分支，所以前面分支中的Hash值尚未删除的可能影响其他分支。（可以自行推推样例1即可发现该问题）
故我们在先序遍历的时候先将这些其他的信息删掉，具体见代码。
同样的右链也类似，不再赘述。
另外此题结点树略多，建议写手工栈。
代码
未加入手工栈：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
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=300005;
int n,m,p[maxn][35],father[maxn],Depth[maxn],Ans[maxn],w[maxn],Hash[maxn*5];
vector<int>LAdd[maxn],LDel[maxn],RAdd[maxn],RDel[maxn];
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Sparse_Table() {
for(int i=1; i<=n; i++)
for(int j=0; j<=log2(n); j++)p[i][j]=-1;
for(int i=1; i<=n; i++)p[i][0]=father[i];
for(int j=1; j<=log2(n); j++)
for(int i=1; i<=n; i++)
if(p[i][j-1]!=-1)p[i][j]=p[p[i][j-1]][j-1];
}
int LCA(int a,int b) {
if(Depth[a]<Depth[b])swap(a,b);
int k=log2(Depth[a]);
for(int i=k; i>=0; i--) {
if(Depth[a]==Depth[b])break;
if(Depth[a]-(1<<i)>=Depth[b])a=p[a][i];
}
if(a==b)return b;
for(int i=k; i>=0; i--)
if(p[a][i]!=-1&&p[a][i]!=p[b][i]) {
a=p[a][i];
b=p[b][i];
}
return p[a][0];
}
void Dfs(int Now,int depth) {
Depth[Now]=depth;
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(Next==father[Now])continue;
father[Next]=Now;
Dfs(Next,depth+1);
}
}
void Query_Left(int Now) {
Ans[Now]-=Hash[Depth[Now]+w[Now]];
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(Next==father[Now])continue;
Query_Left(Next);
}
for(int i=0; i<LAdd[Now].size(); i++)Hash[LAdd[Now][i]]++;
Ans[Now]+=Hash[Depth[Now]+w[Now]];
for(int i=0; i<LDel[Now].size(); i++)Hash[LDel[Now][i]]--;
}
void Query_Right(int Now) {
Ans[Now]-=Hash[w[Now]-Depth[Now]+maxn*2];
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
if(Next==father[Now])continue;
Query_Right(Next);
}
for(int i=0; i<RAdd[Now].size(); i++)Hash[RAdd[Now][i]+maxn*2]++;
Ans[Now]+=Hash[w[Now]-Depth[Now]+maxn*2];
for(int i=0; i<RDel[Now].size(); i++)Hash[RDel[Now][i]+maxn*2]--;
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
father[1]=-1;
Dfs(1,1);
Sparse_Table();
for(int i=1; i<=n; i++)w[i]=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
int lca=LCA(x,y);
if(y==lca) {
LAdd[x].push_back(Depth[x]);
LDel[y].push_back(Depth[x]);
} else if(x==lca) {
RAdd[y].push_back(Depth[x]-2*Depth[lca]);
RDel[x].push_back(Depth[x]-2*Depth[lca]);
} else {
LAdd[x].push_back(Depth[x]);
LDel[lca].push_back(Depth[x]);
RAdd[y].push_back(Depth[x]-2*Depth[lca]);
RDel[lca].push_back(Depth[x]-2*Depth[lca]);
if(Depth[lca]+w[lca]==Depth[x])Ans[lca]--;
}
}
Query_Left(1);
memset(Hash,0,sizeof(Hash));
Query_Right(1);
for(int i=1; i<=n; i++)printf("%d ",Ans[i]);
return 0;
}
加入手工栈：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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=300005;
int n,m,p[maxn][35],father[maxn],Depth[maxn],Ans[maxn],w[maxn],Hash[maxn*5];
vector<int>LAdd[maxn],LDel[maxn],RAdd[maxn],RDel[maxn];
int Head[maxn],cnt=0;
struct Edge {
int to,next;
} edges[maxn*2];
void AddEdge(int x,int y) {
cnt++;
edges[cnt].to=y;
edges[cnt].next=Head[x];
Head[x]=cnt;
}
void Sparse_Table() {
for(int i=1; i<=n; i++)
for(int j=0; j<=log2(n); j++)p[i][j]=-1;
for(int i=1; i<=n; i++)p[i][0]=father[i];
for(int j=1; j<=log2(n); j++)
for(int i=1; i<=n; i++)
if(p[i][j-1]!=-1)p[i][j]=p[p[i][j-1]][j-1];
}
int LCA(int a,int b) {
if(Depth[a]<Depth[b])swap(a,b);
int k=log2(Depth[a]);
for(int i=k; i>=0; i--) {
if(Depth[a]==Depth[b])break;
if(Depth[a]-(1<<i)>=Depth[b])a=p[a][i];
}
if(a==b)return b;
for(int i=k; i>=0; i--)
if(p[a][i]!=-1&&p[a][i]!=p[b][i]) {
a=p[a][i];
b=p[b][i];
}
return p[a][0];
}
struct St {
int Now,i,depth;
} Stack[maxn*2];
int top=0;
void Dfs(int Now,int depth) {
int i,Next;
START1:
Depth[Now]=depth;
for(i=Head[Now]; i; i=edges[i].next) {
Next=edges[i].to;
if(Next==father[Now])continue;
father[Next]=Now;
Stack[++top]=(St) {
Now,i,depth
};
Now=Next;
depth++;
goto START1;
RET1:
Now=Stack[top].Now;
i=Stack[top].i;
depth=Stack[top].depth;
top--;
}
if(top)goto RET1;
}
void Query_Left(int Now) {
int i,Next;
START2:
Ans[Now]-=Hash[Depth[Now]+w[Now]];
for(i=Head[Now]; i; i=edges[i].next) {
Next=edges[i].to;
if(Next==father[Now])continue;
Stack[++top]=(St) {
Now,i,0
};
Now=Next;
goto START2;
RET2:
Now=Stack[top].Now;
i=Stack[top].i;
top--;
}
for(int i=0; i<LAdd[Now].size(); i++)Hash[LAdd[Now][i]]++;
Ans[Now]+=Hash[Depth[Now]+w[Now]];
for(int i=0; i<LDel[Now].size(); i++)Hash[LDel[Now][i]]--;
if(top)goto RET2;
}
void Query_Right(int Now) {
int i,Next;
START3:
Ans[Now]-=Hash[w[Now]-Depth[Now]+maxn*2];
for(i=Head[Now]; i; i=edges[i].next) {
Next=edges[i].to;
if(Next==father[Now])continue;
Stack[++top]=(St) {
Now,i,0
};
Now=Next;
goto START3;
RET3:
Now=Stack[top].Now;
i=Stack[top].i;
top--;
}
for(int i=0; i<RAdd[Now].size(); i++)Hash[RAdd[Now][i]+maxn*2]++;
Ans[Now]+=Hash[w[Now]-Depth[Now]+maxn*2];
for(int i=0; i<RDel[Now].size(); i++)Hash[RDel[Now][i]+maxn*2]--;
if(top)goto RET3;
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
father[1]=-1;
Dfs(1,1);
Sparse_Table();
for(int i=1; i<=n; i++)w[i]=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
int lca=LCA(x,y);
if(y==lca) {
LAdd[x].push_back(Depth[x]);
LDel[y].push_back(Depth[x]);
} else if(x==lca) {
RAdd[y].push_back(Depth[x]-2*Depth[lca]);
RDel[x].push_back(Depth[x]-2*Depth[lca]);
} else {
LAdd[x].push_back(Depth[x]);
LDel[lca].push_back(Depth[x]);
RAdd[y].push_back(Depth[x]-2*Depth[lca]);
RDel[lca].push_back(Depth[x]-2*Depth[lca]);
if(Depth[lca]+w[lca]==Depth[x])Ans[lca]--;
}
}
Query_Left(1);
memset(Hash,0,sizeof(Hash));
Query_Right(1);
for(int i=1; i<=n; i++)printf("%d ",Ans[i]);
return 0;
}
