SS241017C. 距离（distance）

题意

给你一棵无根树，边有边权。每次操作向集合 \(S\) 里插入一个点对 \((a,b)\) 或询问一个点对 \((x,y)\)。对于询问求 \(\min_{(a,b)\in S} \{dis(a,x)+dis(b,y)\}\)。

solution

先考虑单点插入查询的情况。

相当于存在插入关键点操作，每次询问一个点距离最近的关键点。

好像是个经典题，但是我没做过。处理这样的路径问题可以想到点分治。

每个点分治重心可以处理出离它最近的关键点，因为待修且多次询问，就建出点分树。每次修改 \(\log\) 个点分治祖先，每次询问询问 \(\log\) 层。

这样询问是正确的，因为如果最近的关键点不在你的点分治子树里，离你的点分治祖先最近的结点一定离你最近。因为你必须经过祖先才能到达它。

考虑扩展到点对。首先所有关键点的信息都可以通过维护 \(\log\) 个祖先得到。

求 \(\min(dis(a,x)+dis(b,y))\)，可以搞出它们在点分树上的祖先，算 \(\min(dis(a,p)+dis(x,p)+dis(b,q)+dis(y,q))=\min(dis(a,p)+dep(b,q)+dis(x,p)+dis(y,q))\)，因此可以对插入和询问枚举祖先 \(p,q\)，一共有 \(\log^2\) 对。插入就更新这些祖先对的答案，询问就取 \(\min\) 这些祖先对的答案。

可以在线做，时间和空间都是 \(n\log^2\) 的，但是要使用 \(map\) 映射，容易被卡常。

考虑离线优化空间。

我们一共会用到 \(n\log^2\) 对 \((p,q)\)，可以先离线出要用到哪些 \((p,q)\)，然后对于每个 \(p\) 存下对应的 \((a,b)/(x,y)\)，这样空间是 单 \(\log\) 的，先不存 \(p\)。

然后枚举每个 \(p\)，对于固定的 \(p\)，按时间枚举存下的 \((a,b)/(x,y)\)，然后更新或者查询 \(\log\) 个 \(q\)，这里的点分树空间是 \(O(n)\) 的。枚举下一个 \(p\) 的时候清空点分树。

总时间复杂度 \(O(n \log^2 n)\)，空间 \(O(n\log n)\)。

code

#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
constexpr int N=2e5+7,intinf=0x3f3f3f3f;
constexpr ll llinf=0x3f3f3f3f3f3f3f3f;
#define isdigit(x) (x>='0'&&x<='9')
template <typename T>
inline void read(T &x) {
	x=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}
template <typename T>
inline void write(T x,char ch) {
	static int st[20];
	int top=0;
	do {
		st[top++]=x%10;
		x/=10;
	}while(x);
	while(top) putchar(st[--top]+'0');
	putchar(ch);
}
int op,n,m,u,v,w;
struct edge {
	int to,ne,w;
}e[N<<1];
int cnt,head[N];
void addedge(int u,int v,int w) { e[++cnt]={v,head[u],w}, head[u]=cnt; }
template <typename T>
void _min(T &a,T b) { a=min(a,b); }
template <typename T>
void _max(T &a,T b) { a=max(a,b); }
int dfn[N],gfa[N];
int st[N][20];
ll dep[N];
void dfs(int u,int f) {
	dfn[u]=++dfn[0]; st[dfn[0]][0]=f;
	for(int i=head[u];i;i=e[i].ne) {
		int v=e[i].to;
		if(v==f) continue;
		dep[v]=dep[u]+e[i].w;
		dfs(v,u);
	}
}
int lcamin(int x,int y) { return dfn[x]<dfn[y]?x:y; }
void lcainit() {
	int lg=__lg(n);
	rep(k,1,lg) for(int i=1;i+(1<<k)-1<=n;i++) st[i][k]=lcamin(st[i][k-1],st[i+(1<<(k-1))][k-1]);
}
int getlca(int u,int v) {
	if(u==v) return u;
	int mnx=min(dfn[u],dfn[v])+1,mxx=max(dfn[u],dfn[v]);
	int lg=__lg(mxx-mnx+1);
	return lcamin(st[mnx][lg],st[mxx-(1<<lg)+1][lg]);
}
bool del[N];
int rt,mnrt;
int sum;
int sz[N];
void getroot(int u,int f) {
	sz[u]=1;
	int mxsz=0;
	for(int i=head[u];i;i=e[i].ne) {
		int v=e[i].to;
		if(v==f||del[v]) continue;
		getroot(v,u);
		sz[u]+=sz[v];
		_max(mxsz,sz[v]);
	}
	_max(mxsz,sum-sz[u]);
	if(mxsz<mnrt) rt=u,mnrt=mxsz;
}
void buildtree(int u) {
	del[u]=1;
	for(int i=head[u];i;i=e[i].ne) {
		int v=e[i].to;
		if(del[v]) continue;
		sum=sz[v];
		rt=0;
		mnrt=intinf;
		getroot(v,0);
		gfa[rt]=u;
		buildtree(rt);
	}
}
ll getdis(int u,int v) {
	int lca=getlca(u,v);
	return dep[u]+dep[v]-2*dep[lca];
}
ll ans[N];
ll f[N];
void init() {
	memset(ans,0x3f,sizeof(ans));
	memset(f,0x3f,sizeof(f));
	dfs(1,0);
	lcainit();
	sum=n;mnrt=intinf;
	getroot(1,0);
	buildtree(rt);
}
struct node {
	int op,u,v;
}que[N];
vector<int> vec[N];
void initadd(int u,int i) {
	for(int x=u;x;x=gfa[x]) vec[x].push_back(i);
}
void insert(int u,int a,int b) {
	for(int x=b;x;x=gfa[x]) _min(f[x],getdis(a,u)+getdis(b,x));
}
ll query(int u,int a,int b) {
	ll ans=llinf;
	for(int x=b;x;x=gfa[x]) _min(ans,f[x]+getdis(b,x));
	ans+=getdis(u,a);
	return ans;
}
void clear(int u,int a,int b) {
	for(int x=b;x;x=gfa[x]) f[x]=llinf;
}
int main() {
	#ifdef LOCAL
	// freopen("my.out","w",stdout);
	#else
	freopen("distance.in","r",stdin);
	freopen("distance.out","w",stdout);
	#endif
	read(n),read(m);
	rep(i,1,n-1) {
		read(u),read(v),read(w);
 		addedge(u,v,w),addedge(v,u,w);
	}
	init();
	rep(i,1,m) {
		read(op),read(u),read(v);
		que[i]={op,u,v};
		initadd(u,i);
	}
	rep(i,1,n) {
		for(int x:vec[i]) {
			int op=que[x].op,u=que[x].u,v=que[x].v;
			if(op==1) insert(i,u,v);
			else _min(ans[x],query(i,u,v));
		}
		for(int x:vec[i]) {
			if(que[x].op==1) clear(i,que[x].u,que[x].v);
		}
	}
	rep(i,1,m) 
		if(que[i].op==2) {
			if(ans[i]==ans[0]) puts("-1");
			else write(ans[i],'\n');
		}
}