【JZOJ A组】 大逃杀

Description

自从 Y 君退役之后，她就迷上了吃鸡，于是她决定出一道吃鸡的题。
Y 君将地图上的所有地点标号为 1 到 n，地图中有 n − 1 条双向道路连接这些点，通过一条 双向道路需要一定时间，保证从任意一个点可以通过道路到达地图上的所有点。
有些点上可能有资源，Y 君到达一个有资源的点后，可以选择获取资源来使自己的武力值增 加 wi，也可以选择不获取资源。如果 Y 君获取了一个点上的资源，这个点上的资源就会消失，获 取资源不需要时间。
有些点上可能有敌人，Y 君到达一个有敌人的点后，必须花费 ti 秒伏地与敌人周旋，并最终 将敌人消灭。如果 Y 君消灭了一个点上的敌人，这个点上的敌人就会消失。Y 君不能无视敌人继 续前进，因为这样会被敌人攻击。
如果一个点上既有资源又有敌人，Y 君必须先消灭敌人之后才能获取资源，否则就会被敌人 突袭。
游戏开始时，Y 君可以空降到任意一个点上，接下来，她有 T 秒进行行动，T 秒后她就必须 前往中心区域送快递。Y 君希望她前往中心区域送快递时，武力值尽可能大，请你帮助 Y 君设计 路线，以满足她的要求。你只需输出 T 秒后 Y 君的武力值。

Input

第一行由单个空格隔开的两个正整数 n, T，代表点数和时间。
第二行 n 个由单个空格隔开的非负整数代表 wi，如果 wi = 0 代表该点没有武器，
第三行 n 个由单个空格隔开的非负整数代表 ti，如果 ti = 0 代表该点没有敌人。
接下来 n − 1 行每行由单个空格隔开的 3 个非负整数 a, b, c 代表连接 a 和 b 的双向道路，通 过这条道路需要 c 秒。

Output

输出一行一个整数代表 T 秒后 Y 君的武力值。

Sample Input

17 54
5 5 1 1 1 25 1 10 15 3 6 6 66 4 4 4 4
0 1 3 0 0 0 1 3 2 0 6 7 54 0 0 0 0
1 8 3
2 8 3
8 7 7
7 13 0
7 14 0
15 14 2
16 14 3
17 14 5
7 9 4
9 10 25
10 11 0
10 12 0
7 6 20
3 6 3
3 4 3
3 5 3

Sample Output

68

Data Constraint

思路

这题跟之前叫“餐馆”那题很像。

这题的不同点是

1. 每个点多了一个权值
2. 这是一棵无根树

第一个条件只要计算时加上就好了
可是第二个条件。。。

所以我们要比之前多考虑一种情况

用 f(i, j) 代表进入以 i 为根的子树并回到 i，g(i, j) 代表进入以 i 为根的子树并不回到 i，h(i, j) 代表从以 i 为根的子树内出发，经过 i 并回到以 i 为根的子树内，用 j 秒能得到的最大武力值。

这里一个dfs就可以了。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=377,inf=0x3f3f3f3f;
struct E
{int to,next,v;
}e[maxn*2];
int n,m,a[maxn],t[maxn],f[maxn][maxn][3],list[maxn],cnt=0,d[maxn][3],ans;
void add(int u,int v,int val)
{e[++cnt].to=v; e[cnt].next=list[u]; list[u]=cnt; e[cnt].v=val;
}
void dfs(int u,int fa)
{for(int i=0; i<=m; i++){f[u][i][0]=f[u][i][1]=f[u][i][2]=i>=t[u]?a[u]:-inf;}for(int i=list[u]; i; i=e[i].next){int v=e[i].to;if(v==fa) continue;dfs(v,u);memcpy(d,f[u],sizeof(d));for(int j=0; j<=m; j++) for(int k=0; k<=m-j; k++){int ti;if((ti=j+k+2*e[i].v)<=m){f[u][ti][0]=max(f[u][ti][0],d[j][0]+f[v][k][0]);f[u][ti][1]=max(f[u][ti][1],d[j][1]+f[v][k][0]);f[u][ti][2]=max(f[u][ti][2],d[j][2]+f[v][k][0]);f[u][ti][2]=max(f[u][ti][2],d[j][0]+f[v][k][2]);}if((ti=j+k+e[i].v)<=m){f[u][ti][1]=max(f[u][ti][1],d[j][0]+f[v][k][1]);f[u][ti][2]=max(f[u][ti][2],d[j][1]+f[v][k][1]);}}}ans=max(ans,max(f[u][m][0],max(f[u][m][1],f[u][m][2])));
}
int main()
{scanf("%d%d",&n,&m);for(int i=1; i<=n; i++) scanf("%d",&a[i]);for(int i=1; i<=n; i++) scanf("%d",&t[i]);for(int i=1; i<=n-1; i++){int x,y,v;scanf("%d%d%d",&x,&y,&v);add(x,y,v); add(y,x,v);}dfs(1,0);printf("%d",ans);
}