题意简述

题目链接

　　给定一棵有根树，每次给定k个节点，询问是否存在一条以根节点为一端的链，使得这k个节点到这条链的距离均<=1（只需判断可行性，无需给出方案）。

算法概述

　　思维题一般都需要我们分析出一些题目的性质。

　　这道题最特殊的点显然在于其要求的距离小于等于1，也就是说，这k个点要么在链上，要么在链旁。手动画一画图可以发现，对于这两种情况，都满足这个点的父亲必然在链上。

　　那么问题就转化为了给定k个点，询问这k个点是否均在某条以根节点为一端的链上。由于链的数量可能很多，而且最重要的是链之间会有交集，故我们无法直接处理出每个点所在的链，所以我们需要考虑其他做法。

　　我们可以对给定的k个点按照深度排序，然后依次判断每个点是否在其前一个点的子树中即可。

　　子树很好判断，根据dfs序，节点v在节点u的子树中，当且仅当dfn[u]<=dfn[v]<=dfn[u]+size[u]-1。

参考代码

#include 
#include 
#include 
#include 
using namespace std;
const int N=2e5+10;
struct Edge{
	int to,next;
}edge[N<<1];int idx;
int h[N];

void add_edge(int u,int v){edge[++idx]={v,h[u]};h[u]=idx;}

int siz[N],dep[N],id[N],fa[N],q[N];
int timestamp;
int n,m,k;

void dfs(int p,int f)
{
	id[p]=++timestamp;
	siz[p]=1;
	fa[p]=f;
	dep[p]=dep[f]+1;
	for(int i=h[p];~i;i=edge[i].next)
	{
		int to=edge[i].to;
		if(to==f)continue;
		dfs(to,p);
		siz[p]+=siz[to];
	}
}

bool cmp(int a,int b)
{
	return dep[a]