#1063 : 缩地

描述

编织者是 Dota 系列中的一个伪核，拥有很强的生存能力和线上消耗能力。编织者的代表性技能是缩地。缩地带来的隐身、极限移动速度和伤害让它拥有很高的机动性以及赖线和收割的能力。

假设当前作战区域是一棵有根树，编织者所在的位置为根节点1，树中每个节点，有一个权值vi，代表这个节点的收益。树中的每条边，有一个权值wi，代表每条边的长度。编织者从根结点出发，最远累计移动d 距离时，所能得到的收益的最大值是多少？注意重复经过一个节点收益只能计算一次。

输入

第一行包含一个整数 n (1 ≤ n ≤ 100)，表示节点总数。

接下来的一行，包含 n 个数字，表示一个结点的价值 vi（0 ≤ vi ≤ 2）。

接下来的 n-1 行，每行三个整数 (ai, bi, wi)。表示一条连接 ai, bi 节点的边，边长为 wi (1 ≤ ai, bi ≤ n, 1 ≤ wi ≤ 104)。

接下来的一行包含一个数 q，表示询问总数 (0 ≤ q ≤ 100000)。接下来 q 行，每行包含一个整数 d ( ≤ d ≤ 106)，表示从根结点出发，最远累计移动的距离 d 。

输出

对于每组询问，输出一行表示对应的询问所能得到的最大收益。

样例输入

样例输出

1
1
2

700/3=233.333333333333~~~

设f[x][k][1]表示以x为根的子树，想获得k的收益，还要再回到该节点最少的长度。

f[x][k][0]表示以x为根的子树，想获得k的收益，不用再回到该节点最少的长度。

转移时做个背包，分配j的代价到子节点，具体看代码。

#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=Next[i])
using namespace std;
inline int read() {
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
const int maxn=110;
const int INF=1000000000;
int n,val[maxn],first[maxn],Next[maxn<<1],to[maxn<<1],dis[maxn<<1],e;
void AddEdge(int w,int v,int u) {
    to[++e]=v;dis[e]=w;Next[e]=first[u];first[u]=e;
    to[++e]=u;dis[e]=w;Next[e]=first[v];first[v]=e;
}
int f[maxn][maxn*2][2],A[maxn*2],g[maxn*2][2];
int solve(int x,int fa) {
    ren if(to[i]!=fa) solve(to[i],x);
    f[x][val[x]][0]=f[x][val[x]][1]=0;
    ren if(to[i]!=fa) {
        memcpy(g,f[x],sizeof(g));
        dwn(k,n<<1,0) {
            rep(j,0,k) {
                g[k][0]=min(g[k][0],f[x][k-j][1]+f[to[i]][j][0]+dis[i]);
                g[k][0]=min(g[k][0],f[x][k-j][0]+f[to[i]][j][1]+dis[i]*2);
                g[k][1]=min(g[k][1],f[x][k-j][1]+f[to[i]][j][1]+dis[i]*2);
            }
        }
        memcpy(f[x],g,sizeof(g));
    }
}
int main() {
    n=read();
    rep(i,1,n) val[i]=read();
    rep(i,2,n) AddEdge(read(),read(),read());
    rep(i,1,n) rep(j,0,n<<1) f[i][j][0]=f[i][j][1]=INF;
    solve(1,0);
    rep(i,0,n<<1) A[i]=f[1][i][0];
    dwn(i,(n<<1)-1,0) A[i]=min(A[i],A[i+1]);
    int q=read();
    while(q--) printf("%d
",upper_bound(A,A+n*2,read())-A-1);
    return 0;
}

View Code