伪Top Tree学习笔记
No te eches a la mar !
本文介绍的是静态的以Top Tree的部分思想和结构弄出来的可以维护树上动态DP的全局答案的东西，我也不知道该叫啥，或许就叫静态Top Tree或者是某种全局平衡二叉树，标题叫Top Tree是吸引你点进来的。刚发现似乎也有把AAA树叫做伪Top Tree的，所以这里消歧义一下。
前情提要
万恶之源：「SDOI2017」切树游戏。
这题平凡的做法是用树剖线段树维护动态DP，网络上应该很多题解，这里就不再赘述了。要看题解可以移步这篇immortalCO的博客。
为了试图用一个 $\log$ 做这题，学了个全局平衡二叉树，然后发现全局平衡二叉树没法维护信息不可减的情况。而且就算写了可除的 $\bmod 10007$ 类，仍然需要对于合并信息进行分类讨论啥的……
UOJ上的一篇介绍Top Tree的文章有提到Top Tree可以做这个题。今年集训队论文有一篇就是以Top Tree为主题的，还有一篇借用了Top Tree的rake与compress操作的思想……所以总觉得这是个该学的东西，于是就开坑了orz
然而事实上完整版的Top Tree难以实现，我不觉得我能在考场上写出来，有这时间写Top Tree还不如去做提交答案题。所以这里主要介绍的是静态Top Tree。就像全局平衡二叉树可以看成是静态版本的Link-Cut Tree一样。省去link, cut, expose等操作以后，静态的Top Tree就显得易于实现了。因为主要介绍的不是真正的Top Tree，所以叫做伪Top Tree学习笔记。
因为是学习笔记，所以可能直接扔链接，而不进行具体的介绍，侧重点放在实现细节。毕竟别人造过的轮子，为啥还要自己复读一遍呢……qwq
概述
Top Tree是一类用于维护树上信息的数据结构。Wikipedia: Top Tree
在看下面的内容之前，需要先了解一下
- 簇和一些相关的定义（考虑到收缩过程中边和簇其实很相似，所以下文可能混用）
- rake操作（并一度点操作，以下简称R操作）
- compress操作（缩二度点操作，以下简称C操作）
- Top Tree的应用范畴
这篇negiizhao的博客已经把大部分东西介绍得挺清楚的了。这篇文章同时还有给出很多的例题与应用范围之类的东西。读完基本上能对Top Tree有所了解。其中的Contraction-based top tree一段的内容是本文的主要方法。继续阅读之前，可以先通读上面这篇博客，理解主体思想。但是这篇博客内容比较高级，讲的是真的能动来动去的那种Top Tree，所以这里把一些对本文有用的信息摘录如下，这样我就不用把它们再写一遍了。
我们希望得到一种用于维护树上信息的数据结构，类似于序列上的平衡二叉树。
平衡二叉树每次把序列中的 2 段合并为 1 段，所以可以考虑在树上用类似的做法，把某两个“子树”合并为一个“子树”。
为了维护信息，我们希望这样的“子树”中只有不超过 2 个点和外部的点邻接，我们把这样的“子树”（和两个端点）称为簇（cluster）。
显然，没有进行合并时，所有簇都是表示一个边，表示原树的一个边的簇称为 base cluster。
考虑以下两种操作，它们是树收缩（tree contraction）的两个基本操作，rake 消除一个度为 1 的点，compress 消除一个度为 2 的点，此外这些操作会把两条边替换为一条边。
我们可以把这两种操作看作合并两个簇，显然这两个簇合并之后还是簇。合并后簇中和外部邻接的点是图上新边的端点，所以可以认为这个簇表示新边，我们把表示的边的端点称为簇的端点（endpoint）。显然，这样就可以一直合并到只剩一个簇。
我们可以对树进行若干轮收缩，每轮收缩执行 rake 和 compress 的一个极大独立操作集合，这样 $O(\log n)$ 轮收缩后，树就只剩一条边了。最后这条边对应的簇称为根簇（root cluster）。
收缩过程中，簇的合并结构形成了一个树，我们把这个树称为 top tree。
一个簇对应着原树的一个路径和一个子树，其中路径为两个端点之间的路径。
关于边的信息储存在这条边对应的簇中，关于点的信息在消除这个点之后加入簇中（也就是说，簇内维护的信息，不包括端点上的信息），这在某种意义上类似于 BST。 类似序列上一些问题的做法，我们将会维护簇对应的路径和子树，以及两个端点相关的信息。
Contraction-based top tree
1998年 Holm 和 de Lichtenberg 在他们的硕士论文 Top-trees and dynamic graph algorithms 、2006年 Werneck 在 Design and Analysis of Data Structures for Dynamic Trees 给出了基于收缩的最坏 $O(\log n)$ 的实现。
如之前所说，我们对原树进行若干轮收缩，每轮收缩执行 rake 和 compress 的一个极大独立操作集合，这样可以得到 $O(\log n)$ 层的收缩结构。直接实现即可 $O(n)$ 时间建树。
关于这方面的操作的细节与更多介绍，也可以考虑看2019年国家集训队论文的《〈公园〉命题报告》与《〈基础圆方树练习题〉命题报告》。可是我还是觉得上面提到的那篇blog写得好。
尝试一下
当然，真正的Top Tree是一个支持link, cut, expose等操作的高级玩意儿，可惜我蠢得可爱，一时半会儿根本学不会。但是考虑到大部分题应该都不至于毒瘤到要你维护一个支持link,cut而且信息还不可减的动态DP，对于树的形态固定的题目，我们可以考虑使用静态Top Tree来维护我们的信息。下面的静态Top Tree实现是基于每轮执行极大R操作与C操作集合，进行 $O(\log n)$ 轮收缩的方法的。它本身常数可能比较大（当然应该比LCT小），但是其优势在于可以直观地进行一些DP信息的合并。
理论与思想部分上面已经讲得很清楚了。接下来我们直接上个例题，介绍如何使用Top Tree解决「SDOI2017」切树游戏。在看下面的内容之前，或许你可以先看看这篇immortalCO的题解，至少看到那个不支持修改的 $O((n+\log128)\times128)$ 的做法，了解朴素暴力的工作原理，并且知道如何用FWT优化信息合并中的异或卷积。
首先，我们不难设计出一个初步的想法。记 $f[i][0/1][0/1]$ 为一个多项式，它的第 $j$ 项系数代表编号为 $i$ 的簇，其头与尾的节点是否被包含在连通块内，异或权值为 $j$ 的方案数。合并两个块大致是在做一些异或卷积。
我们先不管具体的合并操作是什么样的，先建出Top Tree再说。考虑其实现。
建树
因为合并两个簇的时候经常要讨论两个簇的那个公共点的情况，所以我们把簇认为是有向的。为了避免不必要的翻转操作，我们可以对于每一条无向边建立正反两个簇，这样就可以保证每次合并都能找到方向正确的簇。在最后我们会得到两棵长得一样的树，不过两棵树上的对应点表示的簇互相是反过来的，我们任意选择一棵即可。
本来正经的实现方法应该是对于每个簇维护欧拉序循环链表，这样能支持link和cut啥的。但是我们不需要link和cut，所以我们每一轮顺序枚举所有点，遇到能够进行R操作或者C操作的就做。
每一轮初始的时候，所有点都是合法点，所有边（簇）都是合法边（簇）。
先讨论R操作的情况。假设我们得到了一个合法的可进行R操作的一度点。我们试图把这个一度点到它相邻点的边rake掉。设一度点为 $u$，它相邻点为 $v$。这里讨论把 $(u,v)$ rake掉的情况，对 $(v,u)$ 进行R操作是同理的。我们任意地指定一条关于 $v$ 的合法边 $(v,w)$，其中 $w\ne u$（如果不存在这样的边就跳过这个R操作），rake进去，删去 $(u,v)$ 和 $(v,w)$。此时我们应该会得到一个新的簇，它是原来两个簇的并，并且端点分别是 $v$ 和 $w$。我们把这个簇丢到一个tmp集合里，因为这个簇目前还不是合法簇。我们得保证这个新簇不会被作为本轮其余操作的对象。
注意到这样操作后，$u$ 点被从树中剥去了，而 $v$ 点和 $w$ 点由于旁边有一条本轮新建的边，所以既不能被rake掉也不能被compress掉，因为如果对它们执行rake或compress操作，就会导致这条边在这轮成为孩子，这是我们所不允许的。事实上，我们可以注意到，如果我们删边不即时修改点度，而是这一轮结束后再修改，那么所有的记录度数与实际边表大小不符的点都是不可rake或compress的点。而显然地，其它所有的一度点与二度点都分别是可rake与compress的。
C操作也是类似的。我们假设要缩掉的二度点是是 $u$，它两边的点是 $x$ 和 $y$，然后我们删去 $(x,u)$ 与 $(u,y)$，并且把簇 $(x,y)$ 丢进tmp集合里。
这样，一轮操作就做完了。我们把tmp集合里的边全部丟回e中，然后更新一下每个点的度数，就可以继续做下一轮了。具体实现可以参见代码。
信息合并
假设根簇是 $(s,t)$。那么我们从 $s$ 出发在原树上dfs，把原树变成有根树。对于每条边，我们令其权值为它的下面那个点的权值。这样我们就把除了根以外的所有点权转化为了边权。在合并的时候，讨论簇的公共点是否选择，可以得到rake操作与compress操作对答案的更新贡献方法。讨论的时候可以通过程序枚举合并类似的分类讨论，具体的方法可以参见代码。我自家还是认为这个讨论比动态DP的那些式子要易于思考一些。设根簇的编号为 $r$，最后我们的答案就是
其中 $w_s$ 是 $s$ 点对应的权值对应的FWT数组。
当然，这算是进行了一些trick式的把点权转化为边权。实际上，不进行这一步转换也是可以做的，如前文所提到的，用在一个点被消除的时候统计入答案的方法就好了。
代码
这份代码过了LOJ上的数据，但是不保证没有奇怪的错误，如果有的话务必把我拍醒w
以及树剖线段树的维护方法针对数据形态自带小常数，而这个做法的log是满的，所以不要指望一个log能比两个log快多少。不过这个做法比较稳定，经测在根号二叉树的数据下会比正常常数的树剖线段树略快。不知道有没啥方法卡慢。
以及我自带大常数体质，如果有啥更小常数的实现请务必考虑教教我qwq
#include<functional>
#include<algorithm>
#include<iterator>
#include<cstring>
#include<cassert>
#include<cstdio>
#include<map>
using namespace std;
const unsigned Ha=10007;
int m;
int fp(int b,int e=Ha-2)
{
int r=1;
for(;e;e>>=1,b=1ll*b*b%Ha)if(e&1)r=1ll*r*b%Ha;
return r;
}
const unsigned rv128=fp(128);
inline unsigned sum(register unsigned a,register unsigned b){return a+b<Ha?a+b:a+b-Ha;}
inline unsigned dif(register unsigned a,register unsigned b){return a-b<Ha?a-b:a-b+Ha;}
struct poly
{
unsigned a[133];
void fwt()
{
for(int i=128;i>>=1;)
for(int j=0;j<128;j+=i+i)
for(int k=0;k<i;++k)
{
register unsigned x=a[j+k],y=a[j+k+i];
a[j+k]=sum(x,y);
a[j+k+i]=dif(x,y);
}
}
void ifwt()
{
fwt();
for(int i=0;i<128;++i)a[i]=a[i]*rv128%Ha;
}
}cero,uno,f[133333][2][2],val[33333],res,QAQ[133];
inline void operator+=(poly&a,const poly&b)
{
for(int i=0;i<128;++i)a.a[i]=sum(a.a[i],b.a[i]);
}
inline poly operator+(const poly&a,const poly&b)
{
poly c;
for(int i=0;i<128;++i)c.a[i]=sum(a.a[i],b.a[i]);
return c;
}
inline poly operator*(const poly&a,const poly&b)
{
poly c;
for(int i=0;i<128;++i)c.a[i]=a.a[i]*b.a[i]%Ha;
return c;
}
map<int,int>e[33333],tmp[33333];//If you want, you can use an unordered map instead.
int ce=1;
int ker[133333],ls[133333],rs[133333],pa[133333];
int deg[33333],rek[33333],mk[33333];
bool qwq[33333];
int rt,s,t;
bool dl[133333],dr[133333];
int comb(int a,int b,int c,bool detl,bool detr)
{
int nv=++ce;
dl[nv]=detl;
dr[nv]=detr;
pa[e[a][b]]=pa[e[b][c]]=nv;
ls[nv]=e[a][b];
rs[nv]=e[b][c];
e[a].erase(b);
e[b].erase(c);
return nv;
}
int n;
void shrink()
{
int dep=0,cp=n;
if(cp==2)//Gotcha!
{
s=1;t=2;
rt=e[1][2];
goto heaven;
}
for(;dep<111;++dep)
{
for(int u=1;u<=n;++u)if(!qwq[u])
{
if(deg[u]==1&&e[u].size()==1)
{
int v=e[u].begin()->first;
if(e[v].size()==1)goto hell;
int w=e[v].begin()->first;
if(w==u)w=(--e[v].end())->first;
tmp[v][w]=comb(u,v,w,0,1);
tmp[w][v]=comb(w,v,u,1,0);
qwq[u]=1;
++mk[v];
--cp;
}
else if(deg[u]==2&&e[u].size()==2)
{
int x=e[u].begin()->first;
int y=(--e[u].end())->first;
tmp[x][y]=comb(x,u,y,1,1);
tmp[y][x]=comb(y,u,x,1,1);
qwq[u]=1;
--cp;
}
hell:;
if(cp==2)//Gotcha!
{
for(int u=1;u<=n;++u)if(tmp[u].size()==1)
{
int v=tmp[u].begin()->first;
e[u][v]=tmp[u][v];
s=u;t=v;
rt=e[u][v];
}
goto heaven;
}
}
for(int i=1;i<=n;++i)
{
for(map<int,int>::iterator it=tmp[i].begin();it!=tmp[i].end();++it)e[i][it->first]=it->second;
deg[i]-=mk[i];
mk[i]=0;
tmp[i].clear();
}
}
heaven:;
assert(dep<=40);//If it's more than 40, you might have made some mistake.
}
void upd(int x)
{
int l=ls[x],r=rs[x];
f[x][0][0]=f[l][0][0]+f[r][0][0];
if(!dr[x])f[x][0][0]+=f[r][0][1];
if(!dl[x])f[x][0][0]+=f[l][1][0];
f[x][0][1]=dr[x]?f[r][0][1]:cero;
f[x][1][0]=dl[x]?f[l][1][0]:cero;
f[x][1][1]=cero;
#define foo(i,j) f[x][dl[x]?i:1][dr[x]?j:1]+=f[l][i][1]*f[r][1][j];
foo(0,0);foo(0,1);foo(1,0);foo(1,1);
}
void extract(int x)
{
if(ker[x])rek[ker[x]]=x;
if(ls[x])
{
extract(ls[x]);
extract(rs[x]);
upd(x);
}
}
struct R{int v,z;}ee[111111];
int K[33333];
void ins(int a,int b)
{
ee[++ce]=(R){b,K[a]};
K[a]=ce;
e[a][b]=ce;
++deg[a];
}
bool tr[111111];
void dfs(int u,int pa)
{
for(int i=K[u];i;i=ee[i].z)
{
if(ee[i].v!=pa)dfs(ker[i]=ker[i^1]=ee[i].v,u);
else tr[i]=1;
}
}
int F()
{
register int c,s;
for(;c=getchar(),!isdigit(c););
for(s=c-'0';c=getchar(),isdigit(c);)s=s*10+c-'0';
return s;
}
int main()
{
int heureuse=scanf("%d%d",&n,&m);
for(int i=0;i<m;++i)
{
QAQ[i].a[i]=1;
QAQ[i].fwt();
}
uno=QAQ[0];
if(n==1)
{
int v;
heureuse=scanf("%d",&v);
int q;
for(int i=scanf("%d",&q);i<=q;++i)
{
char op[11];
int x;
heureuse=scanf("%s%d",op,&x);
if(op[0]=='Q')puts(x==v?"1":"0");
else heureuse=scanf("%d",&v);
}
return 0;
}
for(int i=1;i<=n;++i)
val[i]=QAQ[F()];
for(int i=1;i<n;++i)
{
int a,b;
heureuse=scanf("%d%d",&a,&b);
ins(a,b);
ins(b,a);
}
shrink();
dfs(s,0);
for(int i=2;i<2*n;++i)
{
f[i][0][0]=cero;
f[i][tr[i]^1][tr[i]]=uno;
f[i][tr[i]][tr[i]^1]=val[ker[i]];
f[i][1][1]=val[ker[i]];
}
extract(rt);
int q;
heureuse=scanf("%d",&q);
for(int i=1;i<=q;++i)
{
char op[11];
heureuse=scanf("%s",op);
int x=F();
if(op[0]=='Q')
{
res=f[rt][0][0]+f[rt][0][1]+(f[rt][1][0]+f[rt][1][1])*val[s];
res.ifwt();
heureuse=printf("%u\n",res.a[x]);
}
else
{
val[x]=QAQ[F()];
if(rek[x])
{
int r=rek[x];
f[r][tr[r]][tr[r]^1]=val[x];
f[r][1][1]=val[x];
for(;(r=pa[r]);)upd(r);
}
}
}
int v=heureuse;
return ~~(0*v*0);
}
外部链接
- negiizhao在UOJ博客上的《Top tree 的理论、用法和实现》
- immortalCO在UOJ博客上的《基于变换合并的树上动态 DP 的链分治算法 & SDOI2017 切树游戏（cut）解题报告》
- Wikipedia的Top Tree条目
- EtaoinWu在博客上的《Top Tree 学习笔记》
- 2019年国家集训队论文的《〈公园〉命题报告》与《〈基础圆方树练习题〉命题报告》
- 这些链接中提到的链接。其中有很多论文可以看，这里就不枚举了，因为我一篇都没看过。