1. 题目

传送门= ̄ω ̄=

2. 题解

先遍历一遍图,建立二叉树。
再树型dp即可,对于当前节点,枚举给它左儿子多少,右儿子多少。

代码:

#include <bits/stdc++.h>
using namespace std;
int n,q,f[105][105],l[105],r[105],ld[105],rd[105];
vector<int> g[105],dg[105];
bool book[105];
void init(int u)
{
    book[u]=1;
    for(int i=0;i<g[u].size();i++)
        if(!book[g[u][i]])
        {
            if(!l[u])l[u]=g[u][i],ld[u]=dg[u][i],init(g[u][i]);
            else r[u]=g[u][i],rd[u]=dg[u][i],init(g[u][i]);
        }
}
int dfs(int u,int d)
{
    if(f[u][d]>-1)return f[u][d];
    if(f[u][d]=0,!u||!d)return 0;
    for(int i=0;i<d;i++)
        f[u][d]=
            max(f[u][d],dfs(l[u],i)+dfs(r[u],d-i-1)+ld[u]*(i>0)+rd[u]*(d-i-1>0));
    return f[u][d];
}
int main()
{
    scanf("%d%d",&n,&q),memset(f,-1,sizeof(f));
    for(int i=1,a,b,c;i<n;i++)
        scanf("%d%d%d",&a,&b,&c),
        g[a].push_back(b),g[b].push_back(a),dg[a].push_back(c),dg[b].push_back(c);
    init(1),printf("%d\n",dfs(1,q+1));
    return 0;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *