ACdream 1028 Path

标签：ci ch const int 1028 Path Yes include ACdream

Description

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

Input

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

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

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

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

(1≤n,q≤105,1≤ci≤2) (1≤n,q≤105,1≤ci≤2)

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

好题，因为边权只有1和2两种，所以对于边权和分奇数偶数来讨论，2个1可以组成1个2

这样我们只要知道各自的最大值即可，因为所有比最大值小的，一定可以通过在最大值上减去一定数量的2来得到

这样进行树形dp即可，需要注意的是，输入的l范围未给，这非常坑爹。

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define fi first
#define se second
#define mp(i,j) make_pair(i,j)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-8;
const int INF = 0x7FFFFFFF;
const int mod = 10000;
const int N = 2e5 + 10;
const int read()
{
	char ch = getchar();
	while (ch<'0' || ch>'9') ch = getchar();
	int x = ch - '0';
	while ((ch = getchar()) >= '0'&&ch <= '9') x = x * 10 + ch - '0';
	return x;
}
int T, n, m, x, y, z;
int ft[N], nt[N], u[N], v[N], sz;
int ans[2], dp[N][2];

void dfs(int x, int fa)
{
	dp[x][0] = 0; dp[x][1] = 0;
	loop(i, ft[x], nt)
	{
		if (u[i] == fa) continue;
		dfs(u[i], x);
		rep(j, 0, 1) rep(k, 0, 1)
		{
			if ((dp[x][j] & 1) != j || (dp[u[i]][k] & 1) != k) continue;
			ans[(j + k + v[i]) & 1] = max(ans[(j + k + v[i]) & 1], dp[x][j] + dp[u[i]][k] + v[i]);
		}
		rep(j, 0, 1)
		{
			if ((dp[u[i]][j] & 1) != j) continue;
			dp[x][(j + v[i]) & 1] = max(dp[x][(j + v[i]) & 1], dp[u[i]][j] + v[i]);
		}
	}
	rep(j, 0, 1) ans[j] = max(ans[j], dp[x][j]);
}

int main()
{
	while (scanf("%d%d", &n, &m) != EOF)
	{
		rep(i, 1, n) ft[i] = -1;	
		ans[0] = ans[1] = sz = 0;
		rep(i, 1, n - 1)
		{
			scanf("%d%d%d", &x, &y, &z);
			u[sz] = y;	nt[sz] = ft[x]; v[sz] = z; ft[x] = sz++;
			u[sz] = x;	nt[sz] = ft[y]; v[sz] = z; ft[y] = sz++;
		}
		dfs(1, 0);
		while (m--)
		{
			scanf("%d", &x);
			if (x < 0 || x >= 2 * n - 2) printf("No\n");
			else printf("%s\n", ans[x & 1] < x ? "No" : "Yes");
		}
	}
	return 0;
}

标签：ci,ch,const,int,1028,Path,Yes,include,ACdream
From： https://blog.51cto.com/u_15870896/5838881