YOUSIKI 在 noip2016 的一道《天天爱跑步》的题爆零后,潜心研究树上问题,成为了一代大师,于是皮皮妖为了测验他,出了一道题,名曰《跑步爱天天》。
有一个以 1 为根的有根树,初始每个点都有个警卫,每个警卫会按深度优先的顺序周期性的巡逻以其初始点为根的子树(详见样例解释),一个时刻走且仅走一条边。
YOUSIKI 初始在 x 点,他要到根结点拜访皮皮妖,他会沿着最短路径走,一个时刻走且仅走一条边,当他走到这个点时,如果遇到了警卫,他会消耗 1点妖气将这个警卫杀死,杀死后的警卫就不会在以后的路程中出现。
那么 YOUSIKI 需要消耗几点妖气才能拜访到皮皮妖呢?
输入格式
第一行一个数字 T,表示有 T 组数据。
对于每组数据,第一行一个整数 n,表示树有 n个结点。
接下来 n 行,第 i 行有一个整数 k,表示 i号点儿子个数,接下来 k 个整数,表示 k 个有序儿子 (“有序” 的含义详见样例解释)。
最后一行一个整数 x,表示 YOUSIKI 的出发点。
输出格式
输出 T 行,每行一个整数表示答案。
数据范围
对于 20% 的数据,n≤100。
对于 40% 的数据:n≤2000。
对于另外 10% 的数据:树高 ≤5。
对于另外 10% 的数据:树是一条链。
对于 100% 的数据:T≤10,n≤500000。
样例解释
为了方便,我们把初始在 iii 号点的警卫称为警卫 iii。
警卫 1 的一个周期内的巡逻路线为:1->2->4->2->5->2->1->3->6->3->1。
警卫 2 的一个周期内的巡逻路线为:2->4->2->5->2。
警卫 3 的一个周期内的巡逻路线为:3->6->3。
警卫 4,5,6 一直不动。
YOUSIKI 的路线为:6->3->1。
YOUSIKI 初始在 6 号点,需要杀掉警卫 6。第一时刻他在 3 号点,虽然他和警卫 3 对穿过去,但是由于没有在点上相遇,所以不算相遇。第二时刻他在 1 号点,此时 111 号点没有警卫。
注意
警卫的巡逻是周期性的,例如,初始在 2 号点警卫的巡逻路线为:2->4->2->5->2->4->2->5->2->4->2->5->2->...
输入格式中的 “有序” 指的是比如 1 号点的儿子先输入的 2 再输入的 3,那么 1 号点巡逻时就要先巡逻 2 再巡逻 3。
样例输入
1
6
2 2 3
2 4 5
1 6
0
0
0
6
样例输出
1
我们先把整个树 dfs 一遍,遇到一个点就把这个点记录到一个数组后边,
即求出了树的欧拉序,显然如果不考虑循环的话,guard是在这个序列上每次往后走一个,起始位置就是第i个点第一次出现的位置
假设 YOUSIKI 现在走到了 x 点,过了 t 秒,那么我们在这个序列上遍历 x 出现的所有位置,
并查看这个位置往前 t 个是否为 x 的祖先,如果是,把那个祖先标为1,表示已被消灭
坑点1:因为要按输入顺序遍历子节点,而链式前向星建出的图是从后往前的
所以要把加边的顺序反过来
坑点2:相遇的警卫只能是往下走的,且起始位置为第一个出现的i,所以第前t个
祖先必须是第一个出现的
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct Node
{
int next,to;
}edge[];
int num,head[],dep[],dfn[];
int s,cl,tot,t[],n,ans,f[],st[];
bool vis[],mark[];
int gi()
{
char ch=getchar();
int x=;
while (ch<''||ch>'') ch=getchar();
while (ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x;
}
void add(int u,int v)
{
num++;
edge[num].next=head[u];
head[u]=num;
edge[num].to=v;
}
void dfs(int x)
{int i;
dfn[++tot]=x;f[tot]=;
mark[x]=(x==s);
for (i=head[x];i;i=edge[i].next)
{
int v=edge[i].to;
dep[v]=dep[x]+;
dfs(v);
if (mark[v]) mark[x]=;
dfn[++tot]=x;f[tot]=;
}
if (mark[x]) t[x]=cl++;
}
int main()
{int T,i,j,k,x;
cin>>T;
while (T--)
{
memset(head,,sizeof(head));
num=;cl=;tot=;
memset(mark,,sizeof(mark));
memset(dep,,sizeof(dep));
memset(t,,sizeof(t));
memset(f,,sizeof(f));
n=gi();
for (i=;i<=n;i++)
{
k=gi();
for (j=;j<=k;j++)
{
st[j]=gi();
}
for (j=k;j>=;j--)
add(i,st[j]);
}
s=gi();
dep[]=;
dfs();
ans=;
memset(vis,,sizeof(vis));
int u,v;
for (i=;i<=tot;i++)
{
if (mark[u=dfn[i]]&&i>t[u]&&f[i-t[u]])
if (mark[v=dfn[i-t[u]]]&&dep[v]<=dep[u])
if (vis[v]==)
{
ans++;
vis[v]=;
}
}
cout<<ans<<endl;
}
}