自动搬运

查看原文

来自洛谷，原作者为

	NATO 革命尚未成功，同志仍需努力！

搬运于2025-08-24 22:52:01，当前版本为作者最后更新于2024-07-01 20:49:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

写在前面：

这是不久前笔者与以前的同学胡的一个对于单次询问形如 $\sum\limits_{i=l1}^{r1}\sum\limits_{j=l2}^{r2}val(lca(id_i,id_j))$ 的通用在线 $O(q\sqrt n+n\sqrt n)$ 解法，其中 $id$ 是一个预先给定的对应点编号的任意序列，$val(lca(id_i,id_j))$ 是一个只与 $lca(id_i,id_j),id_i,id_j$ 有关的一个值。

本做法的优势在于不需要使用任何除了“$val(lca(id_i,id_j))$ 是 $lca(id_i,id_j)$ 的 $val$”以外与 $val(lca(id_i,id_j))$ 相关的任何性质，普遍性很强，且不需要进行任何化简，思维上简单粗暴。

后发现在一些题中均有类似解法，但写得没有那么清晰。遂决定在此作文以较为详细地介绍此类解法。

要充分理解此文，您可能需要的前置知识：

分块、常见换根 DP 的用法、任意方法实现的 $O(1)$ 查询 LCA、单调栈建虚树。

思路浅析：

让我们从另外一道题谈起。

P4211，这道题题解区中的第三篇题解提出了一种不同于一般 $O(n \log n^2)$ 的 $O(n\sqrt n)$ 的解法。

其解法即是按编号分块，每次将一个块中的节点标记，然后遍历一遍树，预处理出每个节点子树内被标记的点的数量（下称 $i$ 点子树内被标记的点的数量为 $size_i$），再做一遍换根 DP，预处理出 $i\in\{1,2,...,n\},\sum\limits_{j=l}^{r}val(lca(i,id_j))$ 的值（在上题中即是 $\sum\limits_{j=l}^{r}dep(lca(i,j))$ 的值，其中 $l,r$ 指一个块的边界），再对每个点存的块的答案做一遍前缀和。

具体解释一下上文的换根 DP，当我们换到一个节点 $k$ 时，我们此时即是在求出 $\sum\limits_{j=l}^{r}val(lca(k,id_j))$ 的值，我们将这个东西分作两个部分考虑：第一个部分就是在 $k$ 子树内的所有被标记的点，这个部分的 LCA 就是 $k$ 点本身，是容易统计的；第二个部分即 $k$ 子树外的点，这个部分的答案可以在向下转移时传一个值进行记录，即从一个点 $u$ 转移到 $v$，那么显然 $u$ 子树内除了 $v$ 子树内的标记点与 $v$ 子树内任意一个点的 LCA 即是 $u$，那么给下传的值加上一个 $(sz_u-sz_v)val(u)$ 即可。

对于一个询问 $l,r,z$，调用 $z$ 对应的前缀和答案差分一下，求出 $[l,r]$ 间的整块与 $z$ 的答案，散块使用 $O(1)$ 查询的 LCA 暴力查询即可。

总结一下上述过程，实际上我们就是通过分块和换根 DP 尽可能地在可接受的范围内预处理出尽可能多的答案，这样在询问时就可以对少数“边角料”用相对暴力的方法解决了。

上述即是对该题解内容的详细展开，为的是引出解决 $\sum\limits_{i=l1}^{i=r1}\sum\limits_{j=l2}^{r2}val(lca(id_i,id_j))$ 的解法（这难道不就是解法的绝大部分思路吗）。

现在让我们把视线回到 $\sum\limits_{i=l1}^{i=r1}\sum\limits_{j=l2}^{r2}val(lca(id_i,id_j))$。

我们发现，我们需要解决的问题的形式与 P4211 的形式只是多了一层求和罢了。考虑继续沿用分块的思路，整块对整块、整块对散块和散块对整块均可以很容易地用我们预处理的点对块的答案作前缀和后差分求得，这里不展开，相信读者若是明白了上文分块和换根 DP 在干什么的话是能够轻松实现的。

但是瓶颈在于散块对散块的贡献，我们发现用预处理的答案是无法解决的，而暴力枚举点对的做法显然是会使单次询问复杂度退化为 $O(n)$ 的，该怎么办呢？

我们先不谈分块，回顾一下刚才的换根 DP，我们还可以发现一种 $O(nq)$ 的做法，即将 $[l2,r2]$ 的点标记一下，再像分块预处理那样做换根 DP，在树上 $[l1,r1]$ 的位置统计答案即可。

让我们仔细考虑这个过程，容易发现只有在 $[l2,r2]$ 两两间 LCA 是可能导致换根记录的答案发生变化的。emm...只有关键点和其 LCA 有用，这不是暗示我们建虚树吗！

（下设 $len$ 为 $[l1,r1],[l2,r2]$ 区间总长度）于是我们将 $[l1,r1],[l2,r2]$ 的点建虚树后再跑换根（这里假设可以 $O(len)$ 建虚树），复杂度单次就变为了 $O(len)$ 的！

回到我们要解决的散块对散块，我们发现只要能 $O(len)$ 建虚树问题就解决了，毕竟当块大小为 $O(\sqrt n)$ 时，散块中数的个数是 $O(\sqrt n)$ 的嘛。

翻阅 OI Wiki 可以得知我们知道一种按 dfs 序排序后使用单调栈建虚树的方法，但排序仍然是 $O(len\log len)$。尝试利用我们的分块来优化排序的过程，考虑对块内按 dfs 序排序，询问时对着四个散块排序后对应的块扫一遍合并即可完成排序的工作，然后用单调栈的做法就可以愉快地在 $O(len)$ 的复杂度内建虚树啦（温馨提示：您的常数已上天）。

然后和上文预处理时类似地跑个换根 DP 统计贡献即可。

至此，我们就完成了散块对散块这一瓶颈，于是当块长取到 $O(\sqrt n)$ 时整个问题便可以以 $O(n\sqrt n)$ 的时间复杂度解决了。

不过这个玩意有着显而易见的缺点：

1. 如果块长取到 $O(\sqrt n)$ 的话，不逐块处理空间复杂度同样高达 $O(n\sqrt n)$。

2. 代码难度极高，很容易写错。

3. 常数巨大，以致于可能跑起来比 $O(n\sqrt n\log n)$ 还慢。

4. 容易被某些情况下存在的 $\text{polylog}$ 做法乱杀。

综上所述，本做法就是彻彻底底的小丑做法，建议立刻枪决笔者。

好啦，让我们回过头来看看这篇文章投的题目该怎么做吧，写出形式化题面，即：

规定 $id_1=1$，给出 $id_2,id_3,...,id_{m+1}$ 的值，对于 $r=2,3,...,m+1$ 分别求出下式的值：

$\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{r}dis(id_i,id_j)$

我们发现中间不是我们想要的 $val(lca(id_i,id_j))$ 的形式，简单拆一拆即可：

$\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{r}dis(id_i,id_j)=\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{r}dis(id_i,1)+dis(id_j,1)-2dis(lca(id_i,id_j),1)$

$\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{r}dis(id_i,1)+dis(id_j,1)$ 相信只要是个 OIer 都能知道是 $\sum\limits_{i=1}^{r}2dis(id_i,1)r$，简单预处理一下即可。而 $-2dis(lca(id_i,id_j),1)$ 这一部分就完全和我们 $val(lca(id_i,id_j))$ 相符，套用我们的宇宙无敌究极大常数做法即可。

不过直接块长开 $O(\sqrt n)$ 空间会原地飞升的，实测开个四五百再加点卡常小技巧都是能过的，笔者的一些技巧如下：

1. 注意到分块换根时会递归搜索很多遍，考虑用 dfs 序干掉递归：

   • 对于统计子树内关键点个数，按 dfs 序倒着来即可；
   • 对于从根节点开始换根，记录一下每个节点需要向下转移的值，按 dfs 序正着来即可。

2. 注意到本题只有后面有真正意义上的散块，就别把第一块当作散块计算了，只用后面的部分建虚树。

用了它们，就可以健康地卡入时限啦。

更进一步的卡常和对空间复杂度的优化可参看本文的姊妹篇。

参考代码：

如果对前面的某步有不理解的地方，相信结合代码食用应该都能理解吧（代码中本解法的奇怪函数都注释了的，而且本做法思维难度已经低得不能再低了吧）。

4k 超长代码警告。。。

#include <bits/stdc++.h>
#define ll int
#define INF 2100000000ll
using namespace std;
ll n,m,ss;
ll from[100005],L[251],R[251];
ll head[100005],cnt;
long long val[100005][251],btb[251][251];
ll id[100005],yid[100005];
ll to[100005];
long long sz[100005],ds[100005],dv[100005],ps[100005];
long long order_leaf[100005],order_root[100005],mf[100005],in[100005];
queue<long long>q;
struct ed
{
	ll w,v,next;
}edge[200005];
void add(ll u,ll v,ll w)
{
	edge[++cnt].v=v;edge[cnt].next=head[u];head[u]=cnt;edge[cnt].w=w;
	edge[++cnt].v=u;edge[cnt].next=head[v];head[v]=cnt;edge[cnt].w=w;
}
ll tot,f[200005][20],dep[100005],dfn[100005],lg[200005];
void dfs(ll id,ll fa)
{
	f[dfn[id]=++tot][0]=id;mf[id]=fa;
	for(ll i=head[id];i;i=edge[i].next)
	{
		ll v=edge[i].v,w=edge[i].w;
		if(v==fa)continue;
		dep[v]=dep[id]+1;dv[v]=dv[id]+w;
		dfs(v,id);
		f[++tot][0]=id;
	}
}
ll vis[100005];
void pre(ll id,ll fa)
{
	sz[id]=(vis[id]==2);ds[id]=(vis[id]==2)*dv[id];
	for(ll i=head[id];i;i=edge[i].next)
	{
		ll v=edge[i].v;
		if(v==fa)continue;
		pre(v,id);
		sz[id]+=sz[v];ds[id]+=ds[v];
	}
}//建虚树时的子树内关键点个数处理
long long bv[100005];
void pres()
{
	for(ll i=1;i<=n;++i)sz[i]=0,ds[i]=0,bv[i]=0; 
	for(ll i=1;i<=n;++i)
	{
		ll id=order_leaf[i];
		sz[id]+=(vis[id]==2);ds[id]+=(vis[id]==2)*dv[id];
		sz[mf[id]]+=sz[id];
		ds[mf[id]]+=ds[id];          
	}
}//预处理时的子树内关键点个数处理
void root(ll which_block)
{
	for(ll i=1;i<=n;++i)
	{
		ll id=order_root[i];
		bv[id]=bv[mf[id]]+dv[mf[id]]*(sz[mf[id]]-sz[id]);
		if(to[id])val[to[id]][which_block]=bv[id]+sz[id]*dv[id];
	}
}//预处理时的换根 DP
ll lca(ll u,ll v)
{
	ll un=dfn[u],vn=dfn[v];
	if(un>vn)swap(un,vn);
	ll leg=lg[vn-un+1];
	return dep[f[un][leg]]<dep[f[vn-(1<<leg)+1][leg]]?f[un][leg]:f[vn-(1<<leg)+1][leg];
}//欧拉序求 LCA
ll cmp(ll a,ll b)
{
	return dfn[a]<dfn[b];
}
ll use[805];
long long res;
ll st[805],a;
bool vs[100005];
void block_rt(ll id,ll fa,long long before_val)
{
	if(vs[id])
	res+=before_val+sz[id]*dv[id];
	for(ll i=head[id];i;i=edge[i].next)
	{
		ll v=edge[i].v;
		if(v==fa)continue;
		block_rt(v,id,before_val+(sz[id]-sz[v])*dv[id]);
	}
}//建虚树后的换根
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	ll u,v,w;
	for(ll i=2;i<=n;++i)cin>>u>>v>>w,add(u,v,w);
	id[1]=yid[1]=1;++m;
	for(ll i=2;i<=m;++i)cin>>id[i],to[yid[i]=id[i]]=i;
	dep[1]=1;
	dfs(1,0);
	for(ll i=1;i<=n;++i)++in[mf[i]];
	for(ll i=2;i<=n;++i)
		if(!in[i])q.push(i);
	ll cot=0;
	while(!q.empty())
	{
		ll id=q.front();q.pop();
		order_leaf[++cot]=id;
		for(ll i=head[id];i;i=edge[i].next)
		{
			ll v=edge[i].v;
			if(!--in[v])q.push(v);
		}
	}
	q.push(1);cot=0;
	while(!q.empty())
	{
		ll id=q.front();q.pop();
		order_root[++cot]=id;
		for(ll i=head[id];i;i=edge[i].next)
		{
			ll v=edge[i].v;
			if(v!=mf[id])
			q.push(v);
		}
	}//笔者脑抽用拓扑排序处理的非递归时的更新顺序，直接用 dfs 序即可。
	for(ll i=2;i<=tot;++i)lg[i]=lg[i>>1]+1;
	for(ll i=tot;i;--i)
		for(ll j=1;i+(1<<j)-1<=tot;++j)
			f[i][j]=(dep[f[i][j-1]]<dep[f[i+(1<<(j-1))][j-1]]?f[i][j-1]:f[i+(1<<(j-1))][j-1]);//预处理欧拉序求 LCA 用的 ST 表
	ss=400;
	for(ll i=1;i<=m;++i)from[i]=(i-1)/ss+1;
	for(ll i=1;i<=from[m];++i)L[i]=(i-1)*ss+1,R[i]=i*ss;
	R[from[m]]=m;
	for(ll i=1;i<=from[m];++i)
	{
		for(ll j=L[i];j<=R[i];++j)vis[id[j]]=2;
		pres();
		root(i);
		for(ll j=L[i];j<=R[i];++j)vis[id[j]]=0;
		sort(id+L[i],id+1+R[i],cmp);//块内按 dfs 序排序
	}//分块换根预处理
	memset(head,0,sizeof(head));cnt=0;
	for(ll i=1;i<=m;++i)
		for(ll j=1;j<=from[m];++j)
		val[i][j]+=val[i][j-1],btb[from[i]][j]+=val[i][j];//前缀和预处理整块对整块、散块对整块、散块对散块的答案
	for(ll i=1;i<=m;++i)ps[i]=ps[i-1]+dv[yid[i]];//前缀和本题加的那个 zz 距离
	ll l[3],r[3];
	dfn[0]=INF;
	for(ll t=2;t<=m;++t)
	{
		l[1]=1;r[1]=t;l[2]=1;r[2]=t;
		res=0;
		if(from[t]!=1)
		{
			for(ll i=from[l[1]];i<from[r[1]];++i)res+=btb[i][from[r[2]]-1];
			for(ll i=L[from[r[1]]];i<=r[1];++i)res+=val[i][from[r[2]]-1]*2ll;
		}
		for(ll i=L[from[r[2]]];i<=r[2];++i)vis[yid[i]]=2,vs[yid[i]]=1;
		ll dsc=0;
		for(ll i=L[from[r[2]]];i<=R[from[r[2]]];++i)if(vis[id[i]]==2)use[++dsc]=id[i];//这里由于散块部分相同，写起来相对简单得多，完整散块部分合并可参考下给出的云剪切板内的代码
		st[a=1]=1;head[1]=0;cnt=0;
		for(ll i=1;i<=dsc;++i)
		{
			if(use[i]!=1)
			{
				ll lc=lca(use[i],st[a]);
				if(lc!=st[a])
				{
					while(dfn[lc]<dfn[st[a-1]])
					add(st[a-1],st[a],abs(dv[st[a-1]]-dv[st[a]])),--a;
					if(dfn[lc]!=dfn[st[a-1]])head[lc]=0,add(lc,st[a],abs(dv[lc]-dv[st[a]])),st[a]=lc;
					else add(lc,st[a],abs(dv[lc]-dv[st[a]])),a--;
				}
				st[++a]=use[i],head[use[i]]=0;
			}
		}
		for(ll i=1;i<a;++i)add(st[i],st[i+1],abs(dv[st[i]]-dv[st[i+1]]));//单调栈建虚树
		pre(1,0);
		block_rt(1,0,0);
		for(ll i=L[from[r[1]]];i<=r[1];++i)vs[yid[i]]=vis[yid[i]]=0;
		cout<<(ps[t]*1ll*(r[1]-l[1]+1)-res)*2ll<<'\n';
	}
}

由于本题散块需要写的部分比真正完整的写法简单，故 下给出以 $dep$ 为例求 $\sum\limits_{i=l1}^{i=r1}\sum\limits_{j=l2}^{r2}val(lca(id_i,id_j))$ 的完整代码：

戳这里

本文到此结束，感谢您的耐心阅读！