感谢这道题，让我对静态 Top tree 的理解又上一层楼。

首先我们建立出静态 Top tree。

如何建立

首先按全局平衡二叉树的方法对原树划分，然后轻儿子先把所有簇收缩后 rake 到虚父亲上，对于一条轻儿子全部 rake 完成的重链再用全局平衡二叉树对重链的划分方式把重链上所有边 compress 成一条然后向上递归。

不过对于有多个轻儿子的点显然是有问题的。所以对于多个轻儿子在按照重量选取带权中点，每次按照中点分治，两个分治区间内的轻儿子 rake 成一条，最后再和重儿子 rake 到一起，还是重量平衡的，所以树高 $O(\log n)$。

如何维护信息

找到最大的被给定邻域覆盖的簇，它的自己被完全覆盖，提示我们可以处理出每个邻域的信息，而由于它的父亲没有被完全覆盖，所以 $d < sz_{fa}$，并且在这个簇外的邻域形如以界点为根的子树中深度不超过 $d - dis_{u,v}$ 的所有点的深度信息，而这个深度显然小于 $sz_{fa}$，并且对于一个父亲簇需要处理的界点只有 $4$ 个，而 Top tree 的树高为 $\log n$ 代表其子树大小和为 $O(n \log n)$ 级别。总之，如果我们有办法求出这 $O(n \log n)$ 个信息，就有可能做到快速合并。

由于状态总量很少，考虑 dp。

我们定义 $dp_{u,0/1,i}$ 表示簇 $u$ 的上界点与下界点在其簇内的 $i$ 邻域信息，显然有 $i \leq sz_u$，所以在构建 Top tree 时可以在 rake 与 compress 时暴力合并，总合并量级还是 $O(n \log n)$ 的。同时在这个过程中顺便维护出每个簇所有边集与以其两个界点为点集的信息，

然后考虑换根 dp。

定义 $g_{u,0/1,i}$ 表示簇 $u$ 的上界点与下界点在簇外的 $i$ 邻域信息，我们在知道 $g_{u,0/1,i}$ 与 $f_{ls_{u},0/1.i}$ 后可以 $O(sz_{u})$ 地求出 $g_{u,0/1,i}$ 这个状态数位 $O(sz_u)$ 个的 dp 数组。那么便从上到下的 dp 求解出所有 $g_{u,0/1,i}$。

一些细节

1. 对于 $f_{u,0/1,i}$ 而言若这个邻域包含另一个界点那么代表信息的点集即为两个界点，否则只包含以其为邻域中心的那个界点，对于 $g_{u,0/1,i}$ 而言所有的状态代表的信息的点集都只包含以其为邻域中心的那个界点。

2. 不难发现按照上面的做法一个询问实际上要合并两次，但是我们发现 $g_{u,1,i}$ 总是会与簇 $u$ 内所有边集代表的信息合并，所以可以在预处理时提前合并。

3. 实际上两个 dp 数组都没有必要维护到子树大小，维护到直径即可，但是可能会出现一个邻域覆盖整棵树的情况，所以根簇的直径设置为 $n$ 即可。

代码与转移方程

转移方程通过 compress 与 rake 的过程推导出，具体可见代码。

#ifndef CIRCLE_H
#define CIRCLE_H
#include<vector>
struct info{
  unsigned val;
  unsigned poi[2];
};
const info emptyinfo=info{0,(unsigned)-1,(unsigned)-1};
info MR(info a,info b);
info MC(info a,info b);
void init(int T,int n,int q,std::vector<int>dad,std::vector<info>ve,int M);
bool isempty(info a);
info ask(int x,int d);
#endif
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+114;
vector<int> E[maxn];
info edge[maxn];//点 i 到其父亲的信息
struct node{
	int u,v,id,dis;//包括界点
	int len,maxu,maxv;//维护直径
	vector<info> fu,fv,gu,gv;//子树内距离两个界点 k 邻域信息/子树外距离两个界点 k 邻域信息 第一个处理到自己簇大小 第二个处理到父亲簇大小
	info all;//整个簇的信息
 	char type;
	//u 在上面 v 在下面
}cluster[maxn];
int pos[maxn],fa[maxn],ls[maxn],rs[maxn];//pos 表示每个点所在的最小簇
char type[maxn];//P 是边点 C 是 compress 点 R 是 rake 点
int root=1;//根簇
info R(info a,info b){
    if(isempty(a)==true) return b;
    if(isempty(b)==true) return a;
    return MR(a,b);
}
info C(info a,info b){
    if(isempty(a)==true) return b;
    if(isempty(b)==true) return a;
    return MC(a,b);
}
info queryf(node &u,int p,char type){
    if(p>=(int)u.fu.size()) p=(int)u.fu.size()-1;
    if(p<0) return emptyinfo;
    else return (type=='u'?u.fu[p]:u.fv[p]);
}
info queryg(node &u,int p,char type){
    if(p>=(int)u.gu.size()) p=(int)u.gu.size()-1;
    if(p<0) return emptyinfo;
    else return (type=='u'?u.gu[p]:u.gv[p]);
}
void compress(node &x,node &y,node &w){
	//x 在上面 y 在下面
	w.u=x.u,w.v=y.v;
    w.len=max(max(x.len,y.len),x.maxv+y.maxu);
    w.maxu=max(x.maxu,x.dis+y.maxu);
    w.maxv=max(y.maxv,y.dis+x.maxv);
    w.dis=x.dis+y.dis;
    w.all=C(x.all,y.all);
    w.fu.push_back(emptyinfo);
    w.fv.push_back(emptyinfo);
    for(int i=1;i<=w.len;i++){
        w.fu.push_back(C(queryf(x,i,'u'),queryf(y,i-x.dis,'u')));
        w.fv.push_back(C(queryf(x,i-y.dis,'v'),queryf(y,i,'v')));
    }
	fa[x.id]=fa[y.id]=w.id;
	ls[w.id]=x.id;
	rs[w.id]=y.id;
	w.type='C';
	root=w.id;
}
void rake(node &x,node &y,node &w){
	//把 x rake 到 y 上
	w.u=y.u,w.v=y.v;
	w.len=max(max(x.len,y.len),y.maxu+x.maxu);
    w.maxu=max(x.maxu,y.maxu);
    w.maxv=max(y.maxv,x.maxu+y.dis);
	w.dis=y.dis;
	w.all=R(y.all,x.all);
	w.fu.push_back(emptyinfo);
	w.fv.push_back(emptyinfo);
	for(int i=1;i<=w.len;i++){
        w.fu.push_back(R(queryf(y,i,'u'),queryf(x,i,'u')));
        w.fv.push_back(R(queryf(y,i,'v'),queryf(x,i-y.dis,'u')));
    }
	fa[x.id]=fa[y.id]=w.id;
	ls[w.id]=x.id;
	rs[w.id]=y.id;
	w.type='R';
	root=w.id;
}
int father_pos[maxn];//一个点到其父亲的边的簇编号
int father[maxn];
int son[maxn],sz[maxn],tot,dep[maxn];
int top[maxn];
vector<int> st[maxn];//重链上的点存到链顶
void dfs1(int u){
	sz[u]=1;
	for(int v:E[u]){
        dep[v]=dep[u]+1;
        father[v]=u;
		father_pos[v]=++tot;
		pos[u]=pos[v]=tot;
		cluster[tot].u=u,cluster[tot].v=v,cluster[tot].id=tot,cluster[tot].dis=1,cluster[tot].len=1,cluster[tot].maxu=1,cluster[tot].maxv=1,cluster[tot].all=edge[v],cluster[tot].fu.push_back(emptyinfo),cluster[tot].fu.push_back(edge[v]),cluster[tot].fv.push_back(emptyinfo),cluster[tot].fv.push_back(edge[v]);
		dfs1(v);
		if(sz[v]>sz[son[u]]) son[u]=v;
		sz[u]+=sz[v];
	}
}
void dfs2(int u,int tp){
    top[u]=tp;
	st[tp].push_back(u);
	if(son[u]!=0) dfs2(son[u],tp);
	for(int v:E[u]){
		if(v==son[u]) continue;
		dfs2(v,v);
	}
}
int LCA(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=father[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    return v;
}
int dis(int u,int v){
    return dep[u]+dep[v]-2*dep[LCA(u,v)];
}
vector<int> vec[maxn];
vector<int> pre[maxn];
int solve(int l,int r,int u){
	if(l==r) return father_pos[vec[u][l]];
	int L=l,R=r;
	while(L+1<R){
		int mid=(L+R)>>1;
		if((pre[u][mid]-pre[u][l-1])*2<=(pre[u][r]-pre[u][l-1])) L=mid;
		else R=mid;
	}
	int mid=L;
	int lson=solve(l,mid,u);
	int rson=solve(mid+1,r,u);
	int res=++tot;
	cluster[tot].id=tot;
	rake(cluster[lson],cluster[rson],cluster[res]);
	return res;
}
int calc(int l,int r,int u){
    if(l==r) return father_pos[vec[u][l]];
	int L=l,R=r;
	while(L+1<R){
		int mid=(L+R)>>1;
		if((pre[u][mid]-pre[u][l-1])*2<=(pre[u][r]-pre[u][l-1])) L=mid;
		else R=mid;
	}
	int mid=L;
	int lson=calc(l,mid,u);
	int rson=calc(mid+1,r,u);
	int res=++tot;
    cluster[tot].id=tot;
	compress(cluster[lson],cluster[rson],cluster[res]);
	return res;
}
void dfs3(int u){
	for(int x:st[u]){
        if(son[x]==0) continue;
		pre[x].push_back(0);
		vec[x].push_back(0);
		for(int v:E[x]){
			if(v!=son[x]){
				dfs3(v);
				//收缩 (x,v) 一个簇
				vec[x].push_back(v);
			}
		}
		//在对这些轻儿子簇按中点分治的方法合并起来
		for(int i=1;i<=(int)vec[x].size()-1;i++){
			pre[x].push_back(pre[x][i-1]+sz[vec[x][i]]);
		}
		if(vec[x].size()>=2){
            int rt=solve(1,(int)vec[x].size()-1,x);
            if(rt!=0){
                tot++;
                cluster[tot].id=tot;
                rake(cluster[rt],cluster[father_pos[son[x]]],cluster[tot]);
                father_pos[son[x]]=tot;//rake 到重链上
            }
		}
	}
	vec[u].clear();
	pre[u].clear();
	pre[u].push_back(0);
	vec[u].push_back(0);
	for(int x:st[u]){
		vec[u].push_back(x);
	}
	for(int i=1;i<=(int)vec[u].size()-1;i++){
		pre[u].push_back(pre[u][i-1]+sz[father[vec[u][i]]]-sz[vec[u][i]]);
	}
	if(u!=1) father_pos[u]=calc(1,(int)vec[u].size()-1,u);//把重链上的边 compress 成一条
	else father_pos[u]=calc(2,(int)vec[u].size()-1,u);
	E[u].clear();
	E[u].push_back(father[u]);
	return ;
}
void DP(int u){
    if(ls[u]==0) return ;
    if(cluster[u].type=='C'){
        cluster[ls[u]].gu.push_back(emptyinfo);
        cluster[ls[u]].gv.push_back(emptyinfo);
        for(int i=1;i<=cluster[u].len;i++) cluster[ls[u]].gu.push_back(queryg(cluster[u],i,'u')),cluster[ls[u]].gv.push_back(C(queryf(cluster[rs[u]],i,'u'),queryg(cluster[u],i-cluster[rs[u]].dis,'v')));
        cluster[rs[u]].gu.push_back(emptyinfo);
        cluster[rs[u]].gv.push_back(emptyinfo);
        for(int i=1;i<=cluster[u].len;i++) cluster[rs[u]].gu.push_back(C(queryf(cluster[ls[u]],i,'v'),queryg(cluster[u],i-cluster[ls[u]].dis,'u'))),cluster[rs[u]].gv.push_back(queryg(cluster[u],i,'v'));
    }else{
        cluster[ls[u]].gu.push_back(emptyinfo);
        cluster[ls[u]].gv.push_back(emptyinfo);
        for(int i=1;i<=cluster[u].len;i++) cluster[ls[u]].gu.push_back(R(queryg(cluster[u],i,'u'),C(queryf(cluster[rs[u]],i,'u'),queryg(cluster[u],i-cluster[rs[u]].dis,'v')))),cluster[ls[u]].gv.push_back(emptyinfo);
        cluster[rs[u]].gu.push_back(emptyinfo);
        cluster[rs[u]].gv.push_back(emptyinfo);
        for(int i=1;i<=cluster[u].len;i++) cluster[rs[u]].gu.push_back(R(queryg(cluster[u],i,'u'),queryf(cluster[ls[u]],i,'u'))),cluster[rs[u]].gv.push_back(queryg(cluster[u],i,'v'));
    }
    DP(ls[u]);
    DP(rs[u]);
    //默认将界点 u 的簇外信息合并上自己簇的信息
    for(int i=0;i<=cluster[u].len;i++){
        cluster[ls[u]].gu[i]=C(cluster[ls[u]].gu[i],cluster[ls[u]].all);
        cluster[rs[u]].gu[i]=C(cluster[rs[u]].gu[i],cluster[rs[u]].all);
    }
}//Top tree 上换根 dp
char check(node &u,int p){
    if(p==u.u) return 'u';
    else return 'v';
}
info ask(int u, int d){
    if(d==0) return emptyinfo;
    int now=pos[u];
    while(cluster[fa[now]].len<d) now=fa[now];
    return C(queryg(cluster[now],d-dis(cluster[now].u,u),'u'),queryg(cluster[now],d-dis(cluster[now].v,u),'v'));
}
void init(int T, int n, int q, vector<int> FA, vector<info> e, int M){
    for(int i=1;i<n;i++){
        E[FA[i-1]].push_back(i+1);
        edge[i+1]=e[i-1];
    }
    dfs1(1);
    dfs2(1,1);
    dfs3(1);
    DP(root);
    cluster[root].len=n;
    return ;
}

好像有人想要一份更详细一点的题解, 我这里帮出题 青蛙 人写一下吧. 主要叙述通向正解的一些关键点, 所以内容会比本来讲题的课件里少一点.

理解题目

首先要说明的是注意到题意中两个操作的自然性, 所谓的 R 和 C 实际上就是 rake 和 compress 的缩写. 为什么说这两个操作是自然的呢? 因为它几乎就是所谓的 "动态 DP" 支持维护的信息合并的最一般形式了. 按照比较广为人知的方式解释就是, compress 无非是维护链上信息的合并, rake 是将子树信息附着在父亲链上. 此外值得一提的是, 再加上 "twist" 操作则是我们在广义串并联图上能实现的 DP 的信息合并. 在这里附上一张陈年老图:

但也要注意到为了让题目的定义不变得长, 实际上对于信息合并的细节稍微牺牲了一点直观, 也就是一般来说应该是要允许只有一个端点的信息的. 在我们 rake 一个 $\epsilon$ 和一个信息的时候, 按照我们常见的理解应该是返回一个端点的信息, 但在这里不是. 对此可能某些实现时候在这里需要更加精细地处理, 比如用一个结构体把题目给的信息套起来.

树上 DP

我们需要支持有一些序列 $a$, 支持:

• 给出一个信息 $x$, 将所有信息 $a_i$ 变成 $C(x, a_i)$, 然后把 $x$ 放在序列的开头.

• 将两个序列 $a, b$ 合并, 其中先把较短的那个序列用它的最后一个元素补齐, 然后合并成 $R(a_i, b_i)$.

我们直接按照定义对上面的东西暴力 $O(n)$ 做, 就可以求出 $u=1$ 的答案.

自顶向下的时候处理一下前缀和后缀, 就可以 $C_1=O(n^2)$, $C_3=0$ 的情况下求出所有答案了. 此外少加修改, 我们如果只将序列长度保留到 $d$, 就可以完成子任务 C, 因为此时有 $C_1 = O(nd)$.

长链剖分

特殊性质 B 的解法和正解之一有较大的关系. 其实这部分实际上也比较熟知了, 这里仅复述大致思路.

简单来说, 对于前面的树形 DP 问题, 注意到只在所有操作的最后询问. 如果我们总是能 $O(1)$ 支持第一个操作, 并 $O(\min(|a|, |b|))$ 完成第二个操作, 根据简单的贡献分析, 总共的复杂度就是 $O(n)$ 的.

具体的实现是将一个序列实际开成两个数组 $p, q$, 其中一个可以看做某种惰性标记, 实际的 $a_i = q_1 C q_2 C \cdots C q_i C p_i$. 经过较为精细的实现, 就可以完成满足上述复杂度的维护了.

这样我们可以在 $C_1 = O(n), C_3 = 0$ 的情况下通过子任务 B 了.

树的簇 (cluster) 分解

或者说是最为标准的树分块方法. 我们实际上划分的不是树的点集而是边集. 我们称一个连通边集且仅有不超过 $2$ 个界点时是簇 (cluster). 这里界点就是和其他边有交的点. 把边集划分成若干个不交簇的并称为簇分解.

$2$ 个界点的限制, 实际上就是为了让簇分解看成是将树 "收缩" 成了一颗更小的树. 我们总可以将 $1$ 个界点的簇随便补一个界点, 然后将每个簇看做是两个界点间的一条"边".

我们这里还要用到簇的一个性质, 就是可以我们总可以将一颗树划分成 $O(n/d)$ 个大小不超过 $d$ 的簇. 对于这道题来说可能更弱一些, 我们只需要将树划分成 $O(n/d)$ 个直径不超过 $d$ 的簇. 对着这个事实来编一个构造划分的算法其实并不难, 基本上就是一个贪心, 细节在这里略去.

我们考虑固定 $d$ 的时候如何处理所有 $u$ 的询问. 首先将树划分成 $O(n/d)$ 个直径不超过 $d$ 的簇, 当我们询问一个点 $u$ 的时候, $u$ 必然在某个簇的点集内, 由于这个簇的直径不超过 $d$, 所以 $d$-邻域必然完全覆盖这个簇里的所有边! 如果我们已经处理了簇的信息为 $x$, 我们还对于每个簇的界点, 预处理出了两个界点外部子树的信息 $p, q$, 就可以通过计算出 $u$ 到两个界点的距离, 然后将询问的答案表为一个 $p_i C x C q_j$ 了!

我们可以先将每个簇处理出和深度有关的 "大信息", 这是可以通过前述的长链剖分做到 $O(d)$ 的. 然后, 界点外部的信息就可以通过在外面对 "大信息" 做 $O(n/d)$ 个界点构成的边上的树形 DP 来进行维护了. 这样的总复杂度是 $O(n/d)\cdot O(d) = O(n)$.

正解 1 -- 簇内与簇间 DP

我们发现, 前面的处理方法实际上略加修改就可以回答不止一个 $d$. 对于所有 $d\in [L, R]$ 的询问, 我们可以将树分成 $O(n/L)$ 个簇, 然后树形 DP 时候的信息量保留到 $O(R)$, 就是 $O(nR/L)$ 的复杂度进行预处理.

也就是说对每个 $k$, 我们可以 $O(n)$ 预处理 $d\in [2^k, 2^{k+1})$ 的询问. 那么我们就有 $C_1 = O(n\log n), C_3 \leq 1$ 了.

本人实现的就是这种做法, 不过似乎由于某些常数原因, 我需要开成 $4$ 为底数才能获得 $100$ 分.

正解 2 -- top cluster 分解

我们考虑将一颗树每次将两条边进行 rake/compress 让树越来越小的过程, 这个过程整个可以表示成一颗树的结构, 以及所谓的 "top tree". 对于 top tree, 我们可以通过很自然的方式截取出一个簇分解: 拿出 top tree 中大小不超过 $d$ 的所有极大子树.

但是这样的簇的数量能有保证吗? 显然对于随便建的 top tree 是没有的, 但可以证明, 按照全局平衡二叉树的方式构建的 top tree, 能够保证它给出的大小不超过 $d$ 的簇分解有 $O(n/d)$ 个簇.

这样一来, 我们可以直接在这个 top tree 上先自底向上维护出每个簇的簇内信息, 再自顶向下对每个 $d=2^k$ 维护出簇外信息.

这样也足够通过本题, 并且避免了长链剖分的细致讨论.

正解 3 -- 一个更精简的做法

我们忘掉 $[2^k, 2^{k+1})$ 的划分方式, 转而考虑一颗 top tree 本身天然给出的划分.

处理一个询问 $(u, d)$ 的时候, 我们可以先定位到这个点所在的大小不超过 $d$ 的最大子树, 此时 $(u,d)$ 邻域必然是覆盖住这个整个子树所代表的簇的, 而且此时 $d$ 一定小于这个子树的父亲子树的簇的大小.

我们将上一个解法中的自顶向下部分改成: 每个子树维护的簇外信息截取到其父亲的大小, 这样一来, 预处理的信息量实际上就是 $O\left(\sum_{u \in \mathrm{Toptree}} \mathrm{Sub}(u)\right)$, 换句话说, 就是这棵树的 "分治复杂度".

至此我们又丢掉了一个需要的性质, 现在的结论就是: 只要有一个分治复杂度为 $O(n\log n)$ 的, 且分治时只有 $\leq 2$ 个界点的结构, 就给出一个 $C_1 = O(n\log n)$, $C_3\leq 1$ 的处理方法.

当然全局平衡二叉树依然是满足这个条件的, 遗憾的是普及度最高的点分治并不适合处理这个问题, 因为它的分治过程有 $O(\log n)$ 个界点, 这是不构成 top tree 的结构的.

复杂度的最优性

我们最后证明一下在询问只允许 $1$ 次信息合并的时候, 预处理必须有 $\Omega(n\log n)$ 的合并次数, 事实上我们可以证明一条链的情况就已经有此下界.

为了叙述方便, 我们在链上直接说查询 $[l, r]$, 显然这和原问题是相差常数倍等价的. 我们记 $S_{[d/2, d]}$ 为所有点 $x$ 满足预处理的时候得到过一个以 $x$ 为一个端点, 且区间长度在 $[d/2, d]$ 的信息的 $x$.

考虑我们询问所有 $r-l=d$ 的区间, 如果只能进行一次合并, 那么一定是对于某个 $m$ 合并 $[l, m]$ 和 $[m, r]$. 此时必然有 $m-l$ 和 $r-m$ 的一者不小于 $d/2$. 因此, $l,r$ 必有一者在 $S_{[d/2, d]}$ 中. 进一步, 我们可以得到 $S_{[d/2, d]}$ 中必须有 $\Omega(n)$ 个点, 那么长度在 $[d/2, d]$ 中的信息也必须有 $\Omega(n)$ 个被预处理了.

取一系列不交的 $[d/2, d]$, 我们可以取 $\Omega(\log n)$ 个, 这说明了被预处理的信息有 $\Omega(n\log n)$ 个.