hdu5593 树dp详解！！！
题目就是给你一个n点的树，每条边权值为1，对于每个点，求出离这个点距离不超过k的点的个数，然后答案是输出每个点的答案的异或和。
分析，首先他是要求每个点距离不超过k的点数，对于每个点，这个不超过距离k的点数，我们可以从下面（就是这个点的子树去找）， 也可以从这个点的上方去找。
我们分别去考虑。
用f[i][k] 表示从i这个点往下符合条件（距离为k）的点的答案。
对于每个点，先去得到他子树去找到的所有的点。这个就是很经典的树dp做法了，就是去一遍dfs从叶子节点往上去递归回溯更新答案。最底层就是f[i][0~k] = 1;（i是叶子节点）因为从0到k的距离都是只有他本身。对于非叶子节点，我们要去对于这个节点的每个孩子所能贡献的答案去累加也就是f[i][k] = sum(f[z][k-1]),(z是i的所有孩子节点)，k-1是因为从该节点往下面的孩子去需要花费1的价值。
我们得到了f数组后。接下来就考虑对于每一个点往上所能得到的最多答案。
怎么分析呢？
我们设g[i][k]表示i这个节点往上（也就从他的父亲）能延伸得到的符合条件（距离为k）的点的答案
如果我们对于一个节点，找到他父亲的节点往上所能延伸的答案，这样就能得到该节点的答案吗？
我们从5这个节点来看，如果要得到g[5][k](节点5往上去延伸长度为k的点的个数），如果只是去找他父亲（节点2）的g[2][k-1]，那么我们会算漏，算漏的部分就是节点5的父亲节点2的另外的孩子就是2这个节点去往下（不算5）也可以有点是满足的。要怎么得到呢？就是用我们之前找到的f[2][k-1]的总和去减去f[5][k-2]的值就是所有（2节点往下）符合的点的答案，（如果不理解可以手写写看，简单的加减问题）；
所以得到了一个递推式子也就是图中的式子。
如果写呢？就是在跑一次dfs，从上往下更新g数组就可以了。
这样子就能把所有点的答案算出来了。
对于每个点的答案就是g[i][k]+f[i][k]-1;(这个减1还是不减1因人而异，就看你的g有没有多算一遍节点本身。
然后我的程序是所有的g，f数组，都算了所有的1到k的答案，但是从递推式很明显可以看出其实可以优化的不用算那么多。（最多需要算的就只是k-2到k这个区间的就可以了）。
（小坑点！算点的时候要用long long ！！！！）；
如果有问题可以留言，我会尽力解答。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#define ll long long
using namespace std;
const long long max_ = 500000 + 500;
inline int read() {
int s = 0, f = 1;
char ch = getchar();
while (ch<'0' || ch>'9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0'&&ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
int A, B,n,k,xiann = 1,head[max_];
inline int father_(int i) {
// return (A*i + B) % (i - 1) + 1;
return ((A % (i - 1)) *(ll) i % (i - 1) +B % (i - 1)) % (i - 1) + 1;
}
struct v {
int next, to, value;
}xian[2*max_];
inline void add_(int a, int b, int c) {
xian[xiann].next = head[a];
xian[xiann].to = b;
xian[xiann].value = c;
head[a] = xiann;
xiann++;
}
int f[max_][15],g[max_][15];
void dfs(int now, int fa) {
for (int i = 0; i <= k; i++) {
f[now][i] = 1;
}
for (int i = head[now]; i; i = xian[i].next) {
if (xian[i].to != fa) {
dfs(xian[i].to, now);
}
}
for (int z = 1; z <= k ; z++) {
for (int i = head[now]; i; i = xian[i].next) {
if(xian[i].to!=fa)
f[now][z] += f[xian[i].to][z - 1];
}
}
}
void chushihua() {
for (int i = 0; i <= k; i++) {
g[1][i] =1;
}
for (int i = 2; i <= n; i++) {
g[i][0] = 1;
g[i][1] = 2;
}
}
void dfs2(int now, int fa) {
for (int i = head[now]; i; i = xian[i].next) {
if (xian[i].to != fa) {
for (int z = 2; z <= k; z++) {
g[xian[i].to][z] = g[now][z - 1] + f[now][z - 1] - f[xian[i].to][z - 2];
}
}
}
for (int i = head[now]; i; i = xian[i].next) {
if (xian[i].to != fa) {
dfs2(xian[i].to, now);
}
}
}
void qing() {
xiann = 1;
for (int i = 0; i <= n+1; i++) {
head[i] = xian[i].next = xian[i].to = xian[i].value = 0;
for (int j = 0; j <= k + 1; j++) {
f[i][j] = 0; g[i][j] = 0;
}
}
}
int main() {
int T = read();
while (T--) {
qing();
n = read(); k = read(); A = read(); B = read();
//1做根就可以
for (int i = 2; i <= n; i++) {
int t = father_(i);
add_(t, i, 1);
add_(i, t, 1);
}
dfs(1, 0);
chushihua();
dfs2(1, 0);
int ans = f[1][k] ;
for (int i = 2; i <= n; i++) {
ans = ans ^ (f[i][k] + g[i][k] - 1);
}
cout << ans<<endl;
}
return 0;
}
查看23道真题和解析
