P3047 [USACO12FEB]Nearby Cows G
很经典很好的一个树形dp
很明显dp[i][j]表示距离i在范围j以内的权值和
我们还很容易想到维护一个deep[i][j]数组
表示i的子树中距离i在范围j以内的权值和
这个题难就难在距离i在范围j以内的点可能是在i的上头
这时候转移方程就要考虑率容斥一下
对于（u,v）这条边
dp[u][kk]=dp[v][kk-1]-deep[u][kk-2]+deep[u][kk-1];
这个转移方程真的绝绝子，以后很多题目都可以联想到这个方法
还有很多细节在下面代码里面，要想完整写出来确实很有难度
点击查看代码
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=1e5+5;
int val[maxn];
vectorQ[maxn];
int n,k;
int d[maxn][25],dp[maxn][25];
void dfs(int u,int fa,int kk){
d[u][kk]+=val[u];//首先要加上他本身
for(int i=0;i=2)
dp[u][kk]=dp[fa][kk-1]-d[u][kk-2]+d[u][kk];
else
dp[u][kk]=dp[fa][kk-1]+d[u][kk];//在kk<2的情况下，就压根不需要容斥了，dp[fa][kk-1]就没有包括d[u][kk-2]
for(int i=0;i