树形dp
题目大意：
一个n结点的有根树，树边权均为正数，现在有q次询问，每次询问一个距离，问这个距离从0号点出发最多能经过多少点，同一结点多次经过算1次。
n<=500,q<=1000
思路
我们考虑dp，一开始我用dp[i][j]表示i为根的子树走完j的距离后最多还能经过多少节点，不过空间不允许（too young too simple）。考虑点很少，用f[ i ][ j ]表示i为根的子树经过j个节点最小需要多少距离。但是我们考虑可能存在走到深度较深的点，之后回到根节点，再走到其他的点。我们需要加一维[0 /1 ]表示是否要回到根节点，这样逆序递推就能求出。对于每次询问只需要比较一下就好了
转移方程见代码，就是考虑了所有情况。注意枚举（更新）顺序（k从小到大枚举，j从大到小枚举）
code：
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<stack>
#include<cmath>
using namespace std;
const int maxn=2006;
struct hzw
{
int to,next,v;
}e[maxn];
int head[maxn],cur,son[maxn];
inline void add(int a,int b,int c)
{
e[cur].to=b;
e[cur].next=head[a];
e[cur].v=c;
head[a]=cur++;
}
int n,f[maxn][maxn][3];
inline int findson(int s,int fa)
{
son[s]=1;
for (int i=head[s];i!=-1;i=e[i].next)
{
if (e[i].to==fa) continue;
son[s]+=findson(e[i].to,s);
}
return son[s];
}
inline void dfs(int s,int fa)
{
f[s][1][0]=f[s][1][1]=0;
for (int i=head[s];i!=-1;i=e[i].next)
{
if (e[i].to==fa) continue;
dfs(e[i].to,s);
for (int j=son[s];j>=1;--j)
{
for (int k=1;k<=j&&k<=son[e[i].to];++k)
{
f[s][j][1]=min(f[s][j][1],f[s][j-k][1]+f[e[i].to][k][1]+2*e[i].v );
f[s][j][0]=min(f[s][j][0],f[e[i].to][k][0]+f[s][j-k][1]+e[i].v);
f[s][j][0]=min(f[s][j][0],f[e[i].to][k][1]+f[s][j-k][0]+2*e[i].v );
}
}
}
}
signed main()
{
// freopen("violent.in","r",stdin);
int cnt=0;
while (1)
{
int m;
cur=0;
memset(head,-1,sizeof(head));
memset(f,0x3f,sizeof(f));
memset(son,0,sizeof(son));
scanf("%d",&n);
cnt++;
if (n==0) break;
printf("Case %d:
",cnt);
for (int i=1,a,b,c;i<=n-1;++i)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
findson(0,0);
dfs(0,0);
scanf("%d",&m);
for (int i=1,tmp;i<=m;++i)
{
scanf("%d",&tmp);
int ans;
for (int j=n;j>=1;--j) if (f[0][j][0]<=tmp||f[0][j][1]<=tmp) {ans=j;break;}
printf("%d
",ans);
}
}
}
收获：
1、树形dp主要就是考虑出大体的结构，利用dfs逆序（一般是）转移，注意通过数据范围考虑数组的设计。
2、dp的转移顺序十分重要，一定要手模一下。
3、如果对转移方程表示很虚，打个表看看更新情况qwq。