「SDOI2015」寻宝游戏

链接：https://www.luogu.com.cn/problem/P3320

可以发现答案就是求当前存在点所构成最小生成树的边权和的两倍。

那么考虑如何求存在点的最小生成树。

由于原图就是一棵树，那么最小生成树是唯一的，我们考虑把原图以 \(1\) 为根固定下来。那么所有存在点的 lca 一定是在所求得最小生成树上的。又因为存在的点是动态的，我们得找到一种办法维护动态点的 lca，由于 lca 满足结合律，即 \(lca(x,y,z)=lca(lca(x,y),z)=lca(x,lca(y,z))\)。那么我们可以用线段树分治来解决这个问题。

如果用 ST 表来求解 lca，那么动态维护 lca 的复杂度是 \(O(\log n)\)。

然后考虑求最小生成树的边权和。我们可以将边权和转化为点权和。即每个点的点权等于它父亲连向它的那条边的边权。特殊地，对于根 \(1\)，我们规定它的权值为 \(0\)。

那么如何维护最小生成树边权和呢，我们发现最小生成树的边权和可以通过这种方式来求：

将所有存在点到根 \(1\) 的路径上的点染色，那么最小生成树的边权和就是所有被染色的点的点权和再减去 lca 到 \(1\) 路径上的点权和。

前者可以通过树剖加上一个类似于扫描线的线段树维护。

后者可以 dfs 预处理得到。

时间复杂度瓶颈在于树剖，总时间复杂度 \(O(n\log n\log n)\)。

代码如下（树剖的线段树要开 \(8\) 倍不知道为什么）：

#include
#define ll long long
#define ls(k) (k<<1)
#define rs(k) (k<<1|1)
using namespace std;
const int MAXN = 1e5+5;
int n,m;
struct E
{
	int to;ll w;
};
vector  e[MAXN];
int dfn[MAXN],totdfn,dfn1[MAXN<<1],totdfn1,idx[MAXN],idx1[MAXN],match[MAXN];
int siz[MAXN],f[MAXN],son[MAXN],top[MAXN],dep[MAXN],opt[MAXN];
ll V[MAXN],Sum[MAXN],Dis[MAXN];
bool exist[MAXN];
struct lca_ST
{
	int f[21][MAXN<<1],lg[MAXN<<1];
	int Min(int x,int y)
	{
		if(dep[x]<=dep[y]) return x;
		else return y;
	}
	void init()
	{
		for(int i=1;i<=totdfn1;++i) lg[i]=lg[i-1]+(1<r) swap(l,r);int k=lg[r-l+1]-1;
		return Min(f[k][l],f[k][r-(1<siz[son[p]]) son[p]=to;
		dfn1[++totdfn1]=p;
	}
}
void dfs2(int p,int fa,int t)
{
	top[p]=t;dfn[++totdfn]=p;idx[p]=totdfn;
	if(son[p]) dfs2(son[p],p,t);
	for(int i=0;i>1;
		if(le<=mid) upd(le,ri,ls(k),l,mid,c);
		if(ri>mid) upd(le,ri,rs(k),mid+1,r,c);
		pushup(k,l,r);
	}
	void U(int x,int c)
	{
		while(x)
		{
			upd(idx[top[x]],idx[x],1,1,n,c);
			x=f[top[x]];
		}
	}
}T1;
struct Tree_LCA
{
	int node[MAXN<<2];
	Tree_LCA(){memset(node,0,sizeof node);}
	void Add(int le,int ri,int k,int l,int r,int x)
	{
		if(le<=l&&r<=ri) {node[k]=ST.Q(node[k],x);return ;}
		int mid=l+r>>1;
		if(le<=mid) Add(le,ri,ls(k),l,mid,x);
		if(ri>mid) Add(le,ri,rs(k),mid+1,r,x);
	}
	int Q(int pos,int k,int l,int r)
	{
		if(l==r) return node[k];
		int mid=l+r>>1;
		if(pos<=mid) return ST.Q(node[k],Q(pos,ls(k),l,mid));
		else return ST.Q(node[k],Q(pos,rs(k),mid+1,r));
	}
}T2;
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i