首页 > 其他 > 详细

(树形DP) acdream 1028

时间:2015-05-18 12:39:21      阅读:459      评论:0      收藏:0      [点我收藏+]

Path

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

Check if there exists a path of length l in the given tree with weight assigned to each edges.

Input

The first line contains two integers n and q, which denote the number of nodes and queries, repectively.

The following (n1) with three integers ai,bi,ci, which denote the edge between ai and bi, with weight ci.

Note that the nodes are labled by 1,2,,n.

The last line contains q integers l1,l2,,lq, denote the queries.

(1n,q105,1ci2)

Output

For each query, print the result in seperated line. If there exists path of given length, print "Yes". Otherwise, print "No".

Sample Input

4 6
1 2 2
2 3 1
3 4 2
0 1 2 3 4 5

Sample Output

Yes
Yes
Yes
Yes
No
Yes

Source

ftiasch

Manager

 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<vector>
#define INF 100000000
using namespace std;
vector<int> e[100005],w[100005];
int n,q;
int dp[100005][2],val[2];
void dfs(int u,int father)
{
    dp[u][0]=0;
    dp[u][1]=-INF;
    for(int i=0;i<e[u].size();i++)
    {
        int v=e[u][i];
        int ww=w[u][i];
        if(v==father)
            continue;
        dfs(v,u);
        for(int x=0;x<2;x++)
        {
            for(int y=0;y<2;y++)
            {
                val[(x+y+ww)&1]=max(val[(x+y+ww)&1],dp[u][x]+dp[v][y]+ww);
            }
        }
        for(int x=0;x<2;x++)
            dp[u][(x+ww)&1]=max(dp[u][(x+ww)&1],dp[v][x]+ww);
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        e[x].push_back(y);
        e[y].push_back(x);
        w[x].push_back(z);
        w[y].push_back(z);
    }
    val[0]=val[1]=-INF;
    dfs(1,-1);
    while(q--)
    {
        int x;
        scanf("%d",&x);
        if(x<0)
            printf("No\n");
        else
        {
            if(x<=val[x&1])
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
    return 0;
}

  

(树形DP) acdream 1028

原文:http://www.cnblogs.com/water-full/p/4511296.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!