本题的主要难点在于思维
老师讲解图片:
https://www.cnblogs.com/linghusama/gallery/image/458862.html
#include<bits/stdc++.h>
using namespace std;
/*
思维题,主要在于简化复杂度和发现规律
说实话确实没想出来正解,又怕思想是错的,思想参考了题解
(结果证明我想的确实是戳的)
遇到这种题,确实有找规律的思想在里面,因为贡献的条件十分特殊
luogu题解上没有图,这个看着很清晰https://www.cnblogs.com/lfyzoi/p/10221884.html
找到的规律已经写出来了
统计呢?
我总不可能枚举所有点的同时,枚举这个子树内的起点和终点吧
(当然我肯定不看题解就想不到这一点,我肯定会暴力......就算想到这一步也直接做了)
应该类似于逆用了公式吧
桶用法有点难想,主要是怕时间复杂度太高
然鹅...虽然是道思维题
我还是不会写(除了倍增,LCA)
不懂,真的不懂
然后问了游老师,游老师给我讲了个图,希望我看到时能理解吧
里面把一些容易忽略的点给了出来
1.差分统计答案
2.拆路径的注意事项
3.统计多个子树时的差分思想
*/
const int N=300005;
int n,m;
vector<int>mp[N];
vector<int>mp1[N];
vector<int>mp2[N];
int present[N];
int deep[N];
int w[N];
int fa[N][20];
void dfs1(int x){
for(int i=1;(1<<i)<=deep[x];i++){
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for(int i=0;i<mp[x].size();i++){
int to=mp[x][i];
if(to==fa[x][0]){
continue;
}
fa[to][0]=x;
deep[to]=deep[x]+1;
dfs1(to);
}
}
int getlca(int x,int y){
if(x==y){
return x;
}
if(deep[x]<deep[y]){
swap(x, y);
}
int t=log(deep[x]-deep[y])/log(2);
for(int i=t;i>=0;i--){
if(deep[fa[x][i]]>=deep[y]){
x=fa[x][i];
}
if(x==y){
return x;
}
}//到齐平深度
t=log(deep[x])/log(2);
for(int i=t;i>=0;i--){//x和y一起向上跳
if(fa[x][i]!=fa[y][i]){
x=fa[x][i], y=fa[y][i];
}
}
return fa[x][0];
}
int up[N*2],down[N*2];//LCA前和LCA后两个桶
int js[N];//一每个结点作为起点的路径条数
int dist[N],s[N],t[N];//m条路经的长度,起点,终点
int ans[N];//每个节点看到的人数
void dfs2(int x,int faa){
int t1=up[w[x]+deep[x]];
int t2=down[w[x]-deep[x]+N];
for(int i=0;i<mp[x].size();i++){
int to=mp[x][i];
if(to==faa){
continue;
}
dfs2(to,x);
}
up[deep[x]]+=js[x];
for(int i=0;i<mp1[x].size();i++){
int to=mp1[x][i];
down[dist[to]-deep[t[to]]+N]++;
}
ans[x]+=up[w[x]+deep[x]]-t1+down[w[x]-deep[x]+N]-t2;//ans为差值
for(int i=0;i<mp2[x].size();i++){
int to=mp2[x][i];
up[deep[s[to]]]--;
down[dist[to]-deep[t[to]]+N]--;
//清除起点和终点的贡献
}
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=1;i<=n-1;i++){
int u,v;
cin >> u >> v;
mp[u].push_back(v);
mp[v].push_back(u);
}
deep[1]=1;
fa[1][0]=1;
dfs1(1);
for(int i=1;i<=n;i++){
cin >> w[i];
}
for(int i=1;i<=m;i++){
cin >> s[i]>> t[i];
int lca=getlca(s[i],t[i]);
dist[i]=deep[s[i]]+deep[t[i]]-2*deep[lca];
js[s[i]]++;
mp1[t[i]].push_back(i);
mp2[lca].push_back(i);
if(deep[lca]+w[lca]==deep[s[i]]){
ans[lca]--;
}
}
dfs2(1,1);
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
}