题面:
题意:
给定一棵树,点有点权。
给定一个点 x,和一个非负整数 k,问与 x 点相距不超过 k 距离的点的权值和。
其中每条边的距离为1。
题解:
我们设根为 1 号节点。
我们设 dp[x][k] 为 x 点的子树中距离 x 不超过 k 的点的权值和。
对于 dp[x][k]我们只需要维护一个层数的树状数组即可求出。
那么对于我们要求的 ans[x][k] 该怎么处理呢?
观察发现 ans[x][k]=dp[x][k]+(dp[fa[x]][k−1]−dp[x][k−2])+(dp[fa[fa[x]]][k−2]−dp[fa[x]][k−3]).........
所以我们只需要把询问离线,对于每一组 dp[x][k] 拆分为 dp[x][k],dp[fa[x]][k−1],dp[x][k−2],dp[fa[fa[x]]][k−2],dp[fa[x]][k−3].........。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<algorithm>
#define ll long long
#define llu unsigne ll
using namespace std;
const int maxn=1001000;
int head[maxn],ver[maxn<<1],nt[maxn<<1];
int f[maxn],vi[maxn],d[maxn];
int tot=1,n,q;
void add(int x,int y)
{
ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}
void dfs1(int x,int fa)
{
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y==fa) continue;
f[y]=x,d[y]=d[x]+1;
dfs1(y,x);
}
}
ll sum[maxn];
void ad(int x,ll val)
{
for(;x<maxn;x+=(x&(-x)))
sum[x]+=val;
}
ll ask(int x)
{
ll ans=0;
for(;x;x-=(x&(-x)))
ans+=sum[x];
return ans;
}
int u[maxn],k[maxn];
unordered_map<int,ll>mp[maxn];
void init(int n)
{
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)
{
head[i]=0;
mp[i].clear();
}
tot=1,d[1]=1;
}
void dfs2(int x,int fa)
{
for(unordered_map<int,ll>::iterator it=mp[x].begin();it!=mp[x].end();it++)
{
int k=it->first;
it->second-=ask(d[x]+k)-ask(d[x]-1);
}
ad(d[x],vi[x]);
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y==fa) continue;
dfs2(y,x);
}
for(unordered_map<int,ll>::iterator it=mp[x].begin();it!=mp[x].end();it++)
{
int k=it->first;
it->second+=ask(d[x]+k)-ask(d[x]-1);
}
}
int main(void)
{
while(scanf("%d",&n)!=EOF)
{
init(n);
for(int i=1;i<=n;i++)
scanf("%d",&vi[i]);
int x,y;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs1(1,0);
int nu,nk;
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&u[i],&k[i]);
nu=u[i],nk=k[i];
mp[nu][nk]=0;
while(f[nu]&&nk)
{
if(nk-1>=0) mp[f[nu]][nk-1]=0;
if(nk-2>=0) mp[nu][nk-2]=0;
nu=f[nu];
nk--;
}
}
dfs2(1,0);
for(int i=1;i<=q;i++)
{
ll ans=0;
ans+=mp[u[i]][k[i]];
while(f[u[i]]&&k[i])
{
if(k[i]-1>=0) ans+=mp[f[u[i]]][k[i]-1];
if(k[i]-2>=0) ans-=mp[u[i]][k[i]-2];
u[i]=f[u[i]];
k[i]--;
}
printf("%lld\n",ans);
}
}
return 0;
}