UOJ33 【UR #2】树上GCD

感觉像是长剖？具体的，我们思考如何合并两个子树。

因为本质上 gcd 是属于高维前缀和的范畴的，我们使用 \(\text{Dirichlet}\) 后缀和来合并，然后再后缀差分一下。这样我们合并两个子树的复杂度就是 \(O((n+m)\log\log(n+m)\) 的，其中 \(n,m\) 是两棵子树的深度。

但是长剖需要我们快速在链头添加一个数，好像我们使用上面的做法不能轻易加一个值。

考虑了一波，我们对于轻链使用 \(\text{Dirichlet}\) 后缀和来维护，同时枚举其中每一个位置 \(k\) ，那么此时考虑暴力一点的做法就是在重儿子上枚举 \(k\) 的倍数，并查询即可。

考虑这里可以使用根号分治，如果 \(k>\sqrt{n}\) ，那么直接暴力做。如果 \(k\le \sqrt{n}\) ，我们此时可以预处理出重链上的点深度在模 \(k\) 的情况下各个余数的个数，这样我们就可以 \(O(1)\) 查询，同时加入是 \(O(\sqrt{n})\) 的。

感觉这道题目还需要一些 DSU on tree 的技巧，具体来说，就是由于我们那个桶同时只能存入一条重链的信息，所以我们要先处理轻链，然后将轻链从桶中删去，再处理重链（从重儿子处继承），最后再将轻儿子的东西合并上来。

#include
using namespace std;
const int N=2e5+5,B=256;
int n;long long res[N],RES[N];
vector pri;bool tag[N];
void init(int n){
	for(int i=2;i<=n;++i){
		if(!tag[i]) pri.push_back(i);
		for(int j=0;j<(int)pri.size()&&i*pri[j]<=n;++j){
			tag[i*pri[j]]=true;if(i%pri[j]==0) break;
		}
	}
}
struct Edge{int nxt,to;}e[N];int fir[N];
void add(int u,int v,int i){e[i]=(Edge){fir[u],v},fir[u]=i;}
struct Node{int fa,dep,dis,son;}tr[N];
void dfs(int u){
	tr[u].dep=tr[u].dis=tr[tr[u].fa].dep+1;
	for(int i=fir[u];i;i=e[i].nxt){
		int v=e[i].to;if(v==tr[u].fa) continue;
		tr[v].fa=u,dfs(v);
		if(tr[v].dis>tr[tr[u].son].dis)
			tr[u].son=v,tr[u].dis=tr[v].dis;
	}
	// printf("%d %d %d %d\n",u,tr[u].fa,tr[u].dep,tr[u].dis);
}
struct Bag{
	int siz;long long f[B][B],g[N];
	void add(int x,long long y){g[x]+=y;for(int i=1;i h[N];
void Dirichlet(int u){
	int n=h[u].size();
	for(int i=0;i<(int)pri.size()&&pri[i]=1;--j) h[u][j]+=h[u][j*pri[i]];
	}
}
void IDirichlet(int u){
	int n=h[u].size();
	for(int i=0;i<(int)pri.size()&&pri[i]>n,init(n),bag.siz=B;
	for(int i=2,fa;i<=n;++i) scanf("%d",&fa),add(fa,i,i);
	tr[0].dep=-1,dfs(1),DFS(1);
	for(int i=tr[1].dep;i<=tr[1].dis;++i)
		h[1].push_back(bag.g[i]),bag.clear(i);
	for(int i=1;i<(int)h[1].size();++i)
		RES[1]+=h[1][i],RES[i+1]-=h[1][i];
	for(int i=0;i<(int)pri.size()&&pri[i]<=tr[1].dis;++i){
		for(int j=1;j*pri[i]