卧薪尝胆,厚积薄发。
Cuvelia
Date: Mon Mar 11 14:53:44 CST 2019 In Category: NoCategory

Description:

一棵树 $q$ 个询问,每次给出一个点集,询问有多少个点到点集中的点距离相同。
$1\leqslant n\leqslant300000$

Solution:

观察性质题:
性质1:合法的点一定是一个连通块。
因为考虑两个合法的点之间的一条链,如果所有点到这两个点距离相同,那么这条链上的点一定也到所有点距离都相同。
性质2:连通块和点集构成的虚树一定有且仅有一个交点。
肯定不可能有两个交点,而且有一定有交点。
性质3:交点一定是直径的中点。
因为树上任意一点到直径的某一个端点距离最长,所以如果这个点不在直径上那么会形成一个更长的直径。
所以直接找直径中点然后把有标记点的子树删掉就行了,虚树都不用建。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<set>
#include<cctype>
#include<cstring>
using namespace std;
inline int rd()
{
register int res = 0,f = 1;register char c = getchar();
while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}
while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();
return res * f;
}
int n,q;
#define MAXN 300010
struct edge
{
int to,nxt;
}e[MAXN << 1];
int edgenum = 0;
int lin[MAXN] = {0};
void add(int a,int b)
{
e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;
e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;
}
struct seg
{
int l,r,id;
friend bool operator < (const seg &a,const seg &b)
{
return a.r < b.r;
}
};
set<seg> s[MAXN];
int f[MAXN][19],dep[MAXN],siz[MAXN],ind[MAXN],oud[MAXN],tot = 0;
void dfs(int k,int depth)
{
ind[k] = ++tot;
dep[k] = depth;siz[k] = 1;
for(int i = 1;i <= 18;++i)f[k][i] = f[f[k][i - 1]][i - 1];
for(int i = lin[k];i != 0;i = e[i].nxt)
{
if(e[i].to == f[k][0])continue;
f[e[i].to][0] = k;
dfs(e[i].to,depth + 1);
siz[k] += siz[e[i].to];
s[k].insert((seg){ind[e[i].to],oud[e[i].to],e[i].to});
}
oud[k] = ind[k] + siz[k] - 1;
return;
}
int ski(int a,int depth)
{
for(int i = 18;i >= 0;--i)if(dep[f[a][i]] >= depth)a = f[a][i];
return a;
}
int LCA(int a,int b)
{
if(dep[a] < dep[b])swap(a,b);
a = ski(a,dep[b]);
if(a == b)return a;
for(int i = 18;i >= 0;--i)if(f[a][i] != f[b][i])a = f[a][i],b = f[b][i];
return f[a][0];
}
int dis(int a,int b)
{
return dep[a] + dep[b] - 2 * dep[LCA(a,b)];
}
int p[MAXN];
bool vis[MAXN];
int ban[MAXN];
int main()
{
scanf("%d%d",&n,&q);
int a,b;
for(int i = 1;i < n;++i)
{
a = rd();b = rd();
add(a,b);
}
dfs(1,1);
while(q--)
{
p[0] = rd();
for(int i = 1;i <= p[0];++i)p[i] = rd();
if(p[0] == 1){printf("%d\n",n);continue;}
int d;
a = p[1];b = 0;d = -1;
for(int i = 1;i <= p[0];++i)if(dis(p[i],a) > d)d = dis(p[i],a),b = p[i];
a = b;b = 0;d = -1;
for(int i = 1;i <= p[0];++i)if(dis(p[i],a) > d)d = dis(p[i],a),b = p[i];
if(d % 2 == 1){puts("0");continue;}
d /= 2;
int cen = (dep[a] > dep[b] ? ski(a,dep[a] - d) : ski(b,dep[b] - d));
bool tag = true;
for(int i = 1;i <= p[0];++i)if(dis(p[i],cen) != d){tag = false;break;}
if(!tag){puts("0");continue;}
ban[0] = 0;
int ans = n;
for(int i = 1;i <= p[0];++i)
{
if(ind[p[i]] < ind[cen] || ind[p[i]] > oud[cen])
{
if(!vis[f[cen][0]])
{
vis[f[cen][0]] = true;
ban[++ban[0]] = f[cen][0];
ans -= (n - siz[cen]);
}
}
else
{
int id = s[cen].lower_bound((seg){ind[p[i]],ind[p[i]],p[i]}) -> id;
if(!vis[id])
{
vis[id] = true;
ban[++ban[0]] = id;
ans -= siz[id];
}
}
}
printf("%d\n",ans);
for(int i = 1;i <= ban[0];++i)vis[ban[i]] = 0;
ban[0] = 0;
}
return 0;
}
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡