Codeforces Round #629 (Div. 3) E. Tree Queries
题目链接
先处理出每个节点在树内的深度,之前想了一个假算法,就是从节点最深的节点,一直找父亲,但没有考虑到极端情况,就是假设树已经退化成一条链了,但每次只需要找两个节点,一个在最下面,一个在最上面,每次查找的复杂度是O(n)级别的,因为(sum k_i = m)如果(k_i)都为2,查找次数会到达(frac{m}{2})这个算法的整体复杂度就到了O(mn)妥妥的超时了
后来想了LCA的做法,按深度将节点排序好,相邻的那个节点a,b,他们lca的节点,其lca节点的深度一定满足
(depth[a]-depth[lca] <=1) 和 (depth[b]-depth[lca] <=1)
如果不满足的话,就输出NO
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
#define ll long long
#define mk make_pair
const int mod = 1e9+7;
const double pi = acos(-1.0);
vector<int>G[N];
int depth[N],fa[N][22],lg[N],a[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void dfs(int u,int fath)
{
fa[u][0] = fath;
depth[u] = depth[fath] + 1;
for(int i=1;i<=lg[depth[u]];i++)
{
fa[u][i] = fa[fa[u][i-1]][i-1];
}
for(int i=0;i<G[u].size();i++)
{
int v =G[u][i];
if(v!=fath)
dfs(v,u);
}
}
int LCA(int x,int y)
{
if(depth[x]<depth[y])
swap(x,y);
while(depth[x]>depth[y])
{
x = fa[x][lg[depth[x]-depth[y]]-1];
}
if(x==y)
return x;
for(int k=lg[depth[x]]-1;k>=0;k--)
{
if(fa[x][k]!=fa[y][k])
x = fa[x][k],y = fa[y][k];
}
return fa[x][0];
}
int cmp(int x,int y)
{
return depth[x] < depth[y];
}
void init(int n)
{
for(int i=1;i<=n;i++)
{
lg[i] = lg[i-1] + (1 << lg[i-1] == i);
}
}
int main()
{
int n,m;
n =read(),m=read();
init(n);
for(int i=1;i<=n-1;i++)
{
int u,v;
u = read(),v = read();
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,-1);
for(int i=1;i<=m;i++)
{
int k,flag = 1;
k = read();
for(int i=1;i<=k;i++)
{
a[i] = read();
}
sort(a+1,a+k+1,cmp);
if(k==1)
{
puts("YES");
continue;
}
for(int i=1;i<=k-1;i++)
{
int lca = LCA(a[i],a[i+1]);
if(depth[a[i]] - depth[lca] > 1 && depth[a[i+1]] - depth[lca] > 1)
{
flag = 0;
}
}
if(flag == 0)
{
puts("NO");
}
else
{
puts("YES");
}
}
return 0;
}