D. Frog Traveler 1900 dp gq！

https://codeforces.com/contest/1602/problem/D
题解：我们可以通过类似bfs的过程找到每个点的能到达的所需步数最小的点，完成更新，但每个点能被哪些点到达很难判断，故我们反过来考虑，如果我们能得到从n->0的最短跳跃次数，亦得解，而每个点下一步能到达的点容易求解，且为连续的一段序列，故我们可以从底部向上迭代，每次更新只会更新上次更新到的数的上界之上的位置（显然），故我们只会更新每个点1次，复杂度为O(n)。
代码拿了佬的）：

#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;
 
typedef long long LL;
const int MAXN = 300005;
const int INF = 0x3f3f3f3f;
int n;
int a[MAXN],b[MAXN],dis[MAXN],pre[MAXN],to[MAXN],ans[MAXN],anstot;
 
LL Read()
{
	LL x = 0,f = 1; char c = getchar();
	while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
	while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
	return x * f;
}
TT void Put1(T x)
{
	if(x > 9) Put1(x/10);
	putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
	if(x < 0) putchar('-'),x = -x;
	Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
 
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n = Read();
	for(int i = 1;i <= n;++ i) a[i] = Read();
	for(int i = 1;i <= n;++ i) b[i] = Read(); 
	for(int i = 0;i <= n;++ i) dis[i] = INF;
	queue<int> q; q.push(n);
	int MIN = n+1; dis[n] = 0;
	while(!q.empty() && MIN > 0)
	{
		int x = q.front(); q.pop();
		for(int i = x-a[x];i < MIN;++ i)
			if(dis[x]+1 < dis[i+b[i]]) 
				dis[i+b[i]] = dis[x]+1,q.push(i+b[i]),pre[i+b[i]] = i,to[i+b[i]] = x;//pre是滑了之前的，to是从哪里来的 
		MIN = Min(MIN,x-a[x]);
	}
	if(dis[0] == INF) Put(-1,'\n');
	else 
	{
		Put(dis[0],'\n');
		int now = 0;
		while(now != n) ans[++anstot] = pre[now],now = to[now];
		for(int i = anstot;i >= 1;-- i) Put(ans[i],' ');
	}
	return 0;
}

树上背包3 gq!

http://oj.daimayuan.top/course/8/problem/271
题解：我们可以发觉问题的本质是选一些数但要求若儿子选了则父亲必须选取，这种子树关系可以联想到dfs序，我们将树变为dfs序，从后往前进行线性dp，转移决策为选当前节点或者跳过当前子树，即f[i][j]=max(f[i+1][j-w[k]]+a[k],f[i][j])，即可O（nm）完成转移。

#include<bits/stdc++.h>
//#define int long long
#define pb push_back
using namespace std;
const int N=1e3+10;
int a[N],l[N],r[N],w[N],id[N],f[N][10005];
vector<int> g[N];
int tot;
void dfs(int x){
	l[x]=++tot;
	id[tot]=x;
	for(auto it:g[x]){
		dfs(it);
	}
	r[x]=tot+1;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
	int n,q,m;cin>>n>>m;
	for(int i=2;i<=n;i++){
		int x;cin>>x;
		g[x].pb(i);
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++) cin>>w[i];
	dfs(1);
	for(int i=1;i<=m;i++){
		f[n+1][i]=-1e9;
	}
	for(int i=n;i>=1;i--){
		for(int j=0;j<=m;j++){
			int k=id[i],e=id[i+1];
			f[i][j]=f[r[k]][j];
			if(j>=w[k])
			f[i][j]=max(f[i+1][j-w[k]]+a[k],f[i][j]);
		}
	}
	for(int i=0;i<=m;i++){
		if(f[1][i]>=0)
		cout<<f[1][i]<<endl;
		else cout<<0<<endl;
	}
}