【Codeforces Round #629 (Div. 3)E. Tree Queries(树)】题意就是m次询问，问你每次询问的k个点能否都在从根节点到一个点的路径距离1或者就在路径上。
我们发现对于一个节点，如果存在两个以上孙子节点，显然输出NO，那怎么判断何时输出YES呢？显然只要不存在这样两个孙子结点即可，也就是说对于任意节点只可能有多个儿子节点就输出YES，那么判断所有节点的父节点是不是都在一条路径上即可。因为路径可能很长，要用倍增法预处理求出每个点的祖先节点。
#include
using namespace std;
int n,m;
#define MAXN 205000
#define ll long long
int fa[MAXN][30];
vectore[MAXN];
int dep[MAXN];
int step[30];
void dfs(int x,int pre)
{
for(auto it:e[x])
{
if(it==pre)continue;
fa[it][0]=x;
dep[it]=dep[x]+1;
for(int i=1;
step[i]<=dep[it];
i++)
fa[it][i]=fa[fa[it][i-1]][i-1];
dfs(it,x);
}
}
int find(int x,int dep)
{
int pa=x;
for(int i=0;
step[i]<=dep;
i++)
{
if((dep&step[i])==step[i])
pa=fa[pa][i];
}
return pa;
}
int main()
{
step[0]=1;
for(int i=1;
i<=20;
i++)
step[i]=step[i-1]*2ll;
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;
iv;
vector>cmp;
for(int i=0;
i=1;
i--)
{
int now=cmp[i].second;
int pre=cmp[i-1].second;
if(now==pre)continue;
else
{
if(find(now,dep[now]-dep[pre])!=pre)
boolean=0;
}
}
if(boolean)printf("YES\n");
else printf("NO\n");
}
} 推荐阅读
- Codeforces Round #585 (Div. 2) F. Radio Stations
- CodeForces CF #499 Div.2 赛后补题
- #|C. Choosing flowers（枚举+思维+二分）
- #|A. Distance and Axis（思维） Codeforces Round #665 (Div. 2)
- #|D. Distinct Characters Queries（set处理） Codeforces Round #590 (Div. 3)
- #|C. Mere Array（排序+思维） Codeforces Round #665 (Div. 2)
- cf|Codeforces1182E Product Oriented Recurrence(递推+矩乘快速幂）
- cf|Codeforces1182F Maximum Sine (类欧几里得)
- 题解|Codeforces Round #643 (Div. 2)【A—D】
- CodeForces 14B Young Photographer