線段樹合并+樹上差分
個人認為這道題線段樹合并的做法是最簡單的
題意：給一棵樹和 m條路徑，樹上每個點有一個值 \(W_i\) 。問對于每一個點，詢問有多少條路徑的第 \(W_i+1\)個點是這個點。\(n,m \leqslant 1e5\)
假設目前路徑為\(s\)->\(t\)，顯然我們可以預處理出\(lca\)
我們考慮對于每一個節點建立一個權值線段樹，以\(dep\)為下标，每個節點儲存數值i的出現次數，其實我們隻需要葉子結點上的資訊
用樹上差分把鍊的資訊轉化為點
現在對于\(s\)->\(lca\)的路徑，隻需要在\(s\)處的線段樹讓\(dep[s]\)+1，然後每個點統計答案時查詢\(dep[x]+w[x]\)出現了幾次即可即可
對于\(lca\)->\(t\)的路徑，我們想辦法把\(s\)關于\(lca\)翻上去，在在每個點統計dep=dep[x]-w[x]的點有幾個
注意翻上去後d可能變為負的，是以要整體平移一下值域，都加上n即可
/*
天天愛跑步 2019.7.10
給一棵樹和 m條路徑，樹上每個點有一個值 Wi 。問對于每一個點，有多少條路徑的第 Wi+1個點是這個點。
n,m:3e5
*/
#include <cstdio>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
#define rint register int
#define il inline
const int N=3e5+5;
il int read(int x=0,int f=1,char ch='0')
{
while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,m,w[N];
int head[N],ver[N<<1],nxt[N<<1],tot;
il void add(int x,int y){ ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot; }
int dep[N],top[N],son[N],siz[N],fa[N];
void dfs1(int x,int ff)
{
fa[x]=ff; dep[x]=dep[ff]+1; siz[x]=1;
for(rint i=head[x];i;i=nxt[i])
{
int y=ver[i]; if(y==ff) continue;
dfs1(y,x); siz[x]+=siz[y];
if(siz[y]>siz[son[x]]) son[x]=y;
}
}
void dfs2(int x,int topf)
{
top[x]=topf;
if(!son[x]) return ;
dfs2(son[x],topf);
for(rint i=head[x];i;i=nxt[i])
{
int y=ver[i]; if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
il int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]>dep[y] ? y : x;
}
const int M=N*55;
int root[N],lc[M],rc[M],val[M],num;
void update(int &x,int l,int r,int v,int d)
{
if(!x) x=++num;
if(l==r) return (void)(val[x]+=d);
int mid=l+r>>1;
if(v<=mid) update(lc[x],l,mid,v,d);
else update(rc[x],mid+1,r,v,d);
}
int query(int x,int l,int r,int p)
{
if(!x) return 0;
if(l==r) return val[x];
int mid=l+r>>1;
if(p<=mid) return query(lc[x],l,mid,p);
else return query(rc[x],mid+1,r,p);
}
int merge(int a,int b,int l,int r)
{
if(!a || !b) return a+b;
if(l==r)
val[a]+=val[b];
else
{
int mid=l+r>>1;
lc[a]=merge(lc[a],lc[b],l,mid);
rc[a]=merge(rc[a],rc[b],mid+1,r);
}
return a;
}
/*
對于s->lca的路徑，隻需要在s處讓dep[s]+1，然後每個點統計dep=dep[x]+w[x]的點有幾個即可
對于lca->t的路徑，我們想辦法把s關于lca翻上去，在每個點統計dep=dep[x]-w[x]的點有幾個
直接樹上差分即可
注意翻上去後d可能變為負的，是以要整體平移一下
*/
int ans[N];
void dfs(int x)
{
for(rint i=head[x];i;i=nxt[i])
{
int y=ver[i]; if(y==fa[x]) continue;
dfs(y);
root[x]=merge(root[x],root[y],1,n<<1);
}
if(w[x] && n+dep[x]+w[x]<=2*n)//注意要判斷沒有越界
ans[x]+=query(root[x],1,n<<1,n+dep[x]+w[x]);
ans[x]+=query(root[x],1,n<<1,n+dep[x]-w[x]);
}
int main()
{
n=read(); m=read();
for(rint i=1,x,y;i<n;++i) x=read(),y=read(),add(x,y),add(y,x);
dfs1(1,0); dfs2(1,1);
for(rint i=1;i<=n;++i) w[i]=read();
for(rint i=1;i<=m;++i)
{
int x=read(),y=read(); int lca=LCA(x,y);
update(root[x],1,n<<1,n+dep[x],1);
update(root[y],1,n<<1,n+dep[lca]*2-dep[x],1);
update(root[lca],1,n<<1,n+dep[x],-1);
update(root[fa[lca]],1,n<<1,n+dep[lca]*2-dep[x],-1);
}
dfs(1);
for(rint i=1;i<=n;++i)
printf("%d ",ans[i]);
return 0;
}
轉載于:https://www.cnblogs.com/wmq12138/p/11166413.html