题目大意：给定一棵树，每次询问树上包含询问路径上任意至少一点的连通块数
考虑朴素做法，如果我们把询问路径提取出来，以其上每个点为根向非询问路径的点做dfs树形dp，可以求出单独包含该点的方案数，dp方程为
其中， $$$f[p]$$$ 表示以p为根的连通块数目， $$$son(p)$$$ 代表 $$$p$$$ 的子节点(dfs树上的 非原树)集合， $$$+1$$$ 的含义是可以不选这个儿子
获取了询问路径上单独包含每个点的 $$$dp$$$ 值，那么路径总的合法方案可以看做是在这条路径上选取子路径的方案之和，一条子路径的方案为选取子路径上的所有点的$dp$值的乘积，简单来说，把路径看做刚刚序列，答案即为所有区间的乘积之和
暴力计算答案可以递推得来， $$$ans$$$ 表示答案， $$$suf$$$ 表示以当前节点结尾的后缀方案和，初值为 $$$0$$$
按照路径起点到终点的方式累加，因为本人在对拍的时候写了暴力代码，故把这段暴力代码贴出来方便理解：
inline const void dfs(int u,const int &fa)
{
f[u]=1;
for (const int &v:G[u])
if (v!=fa&&!vis[v])
dfs(v,u),
f[u]=mul(f[u],add(f[v],1));
}
int solve(int u,int v)
{
if (dep[u]<dep[v])swap(u,v);
vector<int>path1,path2;
while (dep[u]>dep[v])path1.push_back(u),u=fa[u];
while (u!=v)path1.push_back(u),path2.push_back(v),u=fa[u],v=fa[v];
reverse(path2.begin(),path2.end());
path1.push_back(u);
for (const int &p:path2)path1.push_back(p);
for (const int &p:path1)vis[p]=1;
for (const int &p:path1)dfs(p,0);
int ans(0),suf(0);
for (const int &p:path1)suf=mul(add(suf,1),f[p]),ans=add(ans,suf);
for (const int &p:path1)vis[p]=0;
return ans;
}
如果我们知道了区间的答案，也可以通过合并的方式计算(类似线段树信息合并)
$$$ans[l,r]=ans[l,k-1]+ans[k+1,r]+(suf[l,k-1]+1)\times f[k]\times (pre[k+1,r]+1)$$$
$$$suf[l,r]$$$ 表示区间 $$$[l,r]$$$ 中选取后缀 $$$[i,r](l\leq i\leq r)$$$ 的方案数， $$$pre[l,r]$$$ 同理代表前缀，三项的含义分别为，左半部分的答案，右半部分的答案，包含 $$$k$$$ 的答案
回顾一下我们要干的事，**提取询问路径，由每个点的答案合并成总答案**，是不是感觉一下就上来了，直接采用 $$$lct$$$ 大力提取路径就完事了，节点信息保存路径和子树信息即可
考虑 $$$lct$$$ 节点 $$$p$$$ 上需要存储的信息:
解释一下都有什么用，答案的定义均为在 $$$p$$$ 代表的簇内选取， $$$cnt$$$ 就不用解释了，最后作为最终答案
$$$lcnt,rcnt$$$ 相当于上述暴力做法的 $$$pre$$$ 和 $$$suf$$$
$$$f$$$ 相当于上述暴力做法不管别的 $$$p$$$ 的簇路径节点，包含单个节点 $$$p$$$ 的 $$$dp$$$ 值 $$$f[p]$$$ ，由于各个虚子树由虚子树根路径的左端点(深度最小)连接到 $$$p$$$ 上，故 $$$f$$$ 为 $$$(lcnt+1)$$$ 之积(+1代表不选该虚子树)
$$$F$$$ 目前看起来没有显式作用，但是在维护 $$$lcnt,rcnt$$$ 的时候会用到，等下详细说明
合并方程为($$$pushup(p)$$$):
解释一下，首先 $$$cnt$$$ 的维护很简单经典，跟之前说的合并区间一样的。
维护 $$$lcnt$$$ ，首先继承了左儿子的 $$$lcnt$$$ ，其次考虑跨过 $$$p$$$ 的方案，首先左半部分必须全取，全取的方案数并不是 $$$1$$$ ，而是 $$$son[0]\rightarrow F$$$ ，这里很关键，笔者一开始因为没考虑到这点一直wa2，和暴力对拍半天才发现少了这份贡献。左半部分的簇路径上的所有点的方案数之积才是全取左半簇的答案，所以还需要维护 $$$F$$$ 。 $$$rcnt$$$ 同理， $$$F$$$ 就不用多说了常规路径乘积信息。
然后记得在打路径翻转标记的时候也要翻转交换 $$$lcnt,rcnt$$$
于是我们可以尝试用 $$$lct$$$ 解决此题，在 $$$access$$$ 虚实切换的时候，假如父节点叫 $$$x$$$ ，旧的实右儿子叫 $$$y$$$ ，需要变成 $$$z$$$ ，则有
代表 $$$y$$$ 变虚， $$$z$$$ 变实。噢那么问题来了，题目要求对 $$$998244353$$$ 取模，意思就是 任何值都可能变成 $$$0$$$ ，那么此处除法就会出现除以 $$$0$$$ 的情况，导致无法通过，更变态的是，出题人在题解中提到了刻意构造了 $$$dp$$$ 值为 $$$998244353-1$$$ 的数据，虽然题解的 $$$dp$$$ 值 $$$lct$$$ 无关只是题解方法的东西，但是启示我们并不能简单 $$$lct$$$ 这么做。
为了规避除法，于是我们请出了 $$$Top\ Tree$$$ ，笔者使用的是真 $$$Self-Adjusting \ Top\ Trees$$$
$$$son[2]$$$ 作为 $$$p$$$ 的中儿子，由于 $$$Rake$$$ 节点不用维护 $$$F$$$ ， $$$Compress$$$ 节点不用维护 $$$f$$$ ，调取 $$$son[2]\rightarrow f$$$ 即为前述的 $$$f$$$ ，所以我们把 $$$F$$$ 删去只留 $$$f$$$ ，对于 $$$Compress$$$ 节点使用 $$$f$$$ 代表之前的 $$$F$$$ ，我们写出完整信息合并方程(不了解TopTree的可以把son[2]走中儿子当做虚实切换来理解，Compress(实)节点的虚子树信息存储在son[2]中)
于是可以使用 $$$SATT$$$ 通过此题，时间复杂度 $$$O(n \log n)$$$ 。个人认为采用如此大力数据结构做法比官方题解更好理解直观，就是吃个人算法能力。
#include<cstdio>
#include<algorithm>
using namespace std;
template<class T>inline const void read(T &in)
{
in=0;char ch(getchar());
while (ch<48||ch>57)ch=getchar();
while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
}
constexpr int N(1e5+5),Mod(998244353);
inline const int add(const int &a,const int &b){return a+b>=Mod?a+b-Mod:a+b;}
inline const int mul(const int &a,const int &b){return 1ll*a*b%Mod;}
namespace SelfAdjustingTopTrees
{
constexpr bool Compress(0),Rake(1);
struct Tree
{
bool rev;
int lcnt,rcnt,cnt,f;
Tree *son[3],*fa;
static Tree *Null;
inline void *operator new(size_t size);
inline void *operator new[](size_t size);
inline void operator delete(void *ptr);
inline Tree():rev(0),lcnt(1),rcnt(1),cnt(1),f(1)
{
son[0]=son[1]=son[2]=fa=Null;
}
inline const void reverse()
{
swap(son[0],son[1]);
swap(lcnt,rcnt);
rev^=1;
}
template<const bool type>inline const void pushdown();
template<const bool type>inline const void pushup();
inline const bool isroot()
{
return fa->son[0]!=this&&fa->son[1]!=this;
}
inline const bool id()
{
return fa->son[1]==this;
}
inline const void set(Tree *p,const int &d)
{
(son[d]=p)->fa=this;
}
template<const bool type>inline const void rotate()
{
Tree *fa(this->fa);
fa->pushdown<type>();pushdown<type>();
const bool f(id());
if (fa->fa!=Null)fa->fa->son[fa->fa->son[2]==fa?2:fa->id()]=this;
this->fa=fa->fa;
fa->set(son[f^1],f);
set(fa,f^1);
fa->pushup<type>();pushup<type>();
}
template<const bool type>inline const void splay(Tree *goal=Null)
{
for (pushdown<type>();fa!=goal&&!isroot();rotate<type>())
if (fa->fa!=goal&&!fa->isroot())
fa->fa->pushdown<type>(),
(fa->id()^id()?this:fa)->rotate<type>();
}
template<const bool type,const bool d>inline const void splay_m()
{
Tree *p(this);
while (p->pushdown<type>(),p->son[d]!=Null)p=p->son[d];
p->splay<type>(fa);
}
}*Tree::Null,*node0;
#define Null Tree::Null
#define node(x) (node0+x)
char memoryPool[N*sizeof(Tree)<<1],*tail;
void *recycle[N],**top;
inline void *Tree::operator new(size_t size){return top!=recycle?*--top:tail-=size;}
inline void *Tree::operator new[](size_t size){return tail-=size;}
inline void Tree::operator delete(void *ptr){*top++=ptr;}
inline const void init(const int &n)
{
tail=memoryPool+sizeof(memoryPool);
top=recycle;
Null=new Tree;
Null->cnt=Null->lcnt=Null->rcnt=0;
Null->son[0]=Null->son[1]=Null->son[2]=Null->fa=Null;
node0=new Tree[n+1];
}
template<>inline const void Tree::pushup<Compress>()
{
f=mul(son[0]->f,mul(son[2]->f,son[1]->f));
lcnt=add(son[0]->lcnt,mul(mul(son[0]->f,son[2]->f),add(son[1]->lcnt,1)));
rcnt=add(son[1]->rcnt,mul(mul(son[1]->f,son[2]->f),add(son[0]->rcnt,1)));
cnt=add(add(son[0]->cnt,son[1]->cnt),mul(mul(add(son[0]->rcnt,1),son[2]->f),add(son[1]->lcnt,1)));
}
template<>inline const void Tree::pushup<Rake>()
{
f=mul(mul(son[0]->f,son[1]->f),add(son[2]->lcnt,1));
}
template<>inline const void Tree::pushdown<Compress>()
{
if (rev)
son[0]->reverse(),
son[1]->reverse(),
rev=0;
}
template<>inline const void Tree::pushdown<Rake>(){}
inline const void splice(Tree *p)
{
p->splay<Rake>();
(p=p->fa)->splay<Compress>();
Tree *q(p->son[2]);
q->pushdown<Rake>();
if (p->son[1]!=Null)
swap(p->son[1]->fa,q->son[2]->fa),
swap(p->son[1],q->son[2]);
else
{
p->set(q->son[2],1);
if (q->son[0]!=Null)
q->son[0]->splay_m<Rake,1>(),
q->son[0]->set(q->son[1],1),
p->son[2]=q->son[0];
else
q->son[1]->pushdown<Rake>(),
p->son[2]=q->son[1];
delete q;q=p->son[2];q->fa=p;
}
q->pushup<Rake>();p->pushup<Compress>();
p->son[1]->rotate<Compress>();
}
inline const void access(Tree *p)
{
p->splay<Compress>();
if (p->son[1]!=Null)
{
Tree *q(new Tree);
q->set(p->son[2],0);
q->set(p->son[1],2);
q->pushup<Rake>();
p->son[1]=Null;
p->set(q,2);
p->pushup<Compress>();
}
while (p->fa!=Null)splice(p->fa);
}
inline const void evert(Tree *p)
{
access(p);p->reverse();
}
inline const void expose(Tree *p,Tree *q)
{
evert(p);access(q);
}
inline const int query(Tree *p,Tree *q)
{
expose(p,q);return q->cnt;
}
inline const void link(Tree *p,Tree *q)
{
access(p);evert(q);p->set(q,1);p->pushup<Compress>();
}
// void check(Tree *p,bool type=0){if (p==Null)return;if (type)p->pushdown<Rake>();else p->pushdown<Compress>();check(p->son[0],type);printf("%d %d %d %d %d %d %d %d %d\n",p-node0,p->son[0]-node0,p->son[1]-node0,p->son[2]-node0,p->fa-node0,p->lcnt,p->rcnt,p->cnt,p->f);check(p->son[1],type);check(p->son[2],type^1);}
}
using namespace SelfAdjustingTopTrees;
inline const void work()
{
int n,m;
read(n);read(m);
init(n);
for (int p,i(2);i<=n;i++)
read(p),link(node(p),node(i));
for (int u,v;m--;)
read(u),read(v),printf("%d\n",query(node(u),node(v)));
}
int main()
{
int T;read(T);while (T--)work();
return 0;
}
