题意

给定一棵树，能否找到一条路径$x_0, x_1, x_2\ldots, x_n$，使得$x_0 = 0$，$Set{D(x_i, x_{i+1})} = S$

思路

如果存在长度为$A$的路径，那么一定存在长度为$A-1$的路径。

考虑建一个新的图，使得图中的每条边的长度都在S中，则答案就是询问是否存在一个点$p$，使得能从0沿新的图走到$p$，且满足距离$p$最远的点的距离大于等于$S$中最大的元素。

Code

耗时: 3911 ms

内存: 28192 kB

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2000 + 5;

struct JumpDistancesOnTree{
	vector<int> e[maxn], e2[maxn];
	unordered_set<int> S;
	int dd[maxn], fur[maxn];
	int flag[maxn];
	void getdist(int u)
	{
		memset(dd, 0x3f, sizeof dd);
		dd[u] = 0;
		queue<int> q;
		q.push(u);
		while (!q.empty())
		{
			int u = q.front();q.pop();
			for (int i = 0; i < (int)e[u].size(); i++)
			{
				if (dd[e[u][i]] > dd[u] + 1)
				{
					dd[e[u][i]] = dd[u] + 1;
					q.push(e[u][i]);
				}
			}
		}
	}
	string isPossible(vector<int> p, vector<int> s)
	{
		int mx = 0;
		memset(fur, 0, sizeof fur);
		for (int i = 0; i < (int)s.size(); i++)
			S.insert(s[i]);
		mx = s[s.size() - 1];
		int n = p.size() + 1;
		for (int i = 0; i < (int)p.size(); i++)
		{
			e[p[i]].push_back(i + 1);
			e[i + 1].push_back(p[i]);
		}
		for (int i = 0; i < n; i++)
		{
			getdist(i);
			for (int j = 0; j < n; j++)
			{
				if (S.find(dd[j]) != S.end())
				{
					fur[i] = max(fur[i], dd[j]);
					e2[i].push_back(j);
				}
			}
		}
		queue<int> q;
		q.push(0);
		memset(flag, 0, sizeof flag);
		flag[0] = 1;
		while (!q.empty())
		{
			int u = q.front(); q.pop();
			for (int i = 0; i < (int)e2[u].size(); i++)
			{
				if (!flag[e2[u][i]])
				{
					flag[e2[u][i]] = 1;
					q.push(e2[u][i]);
				}
			}
		}
		for (int i = 0; i < n; i++)
			if (flag[i] && fur[i] >= mx) return "Possible";
		return "Impossible";
	}
};