「UOJ87」mx的仙人掌 - 虚仙人掌/虚圆方树

题目大意

    现给定一棵仙人掌，每条边有一个正整数权值，每次给$k$个点（可以存在相同点），问从它们中选出两个点（可以相同），它们之间最短路的最大值是多少。
    边权不超过$2^{31}-1$，$tot$表示询问的总点数，$n,tot\le300000$

---

题目分析

对于总结点的限制，不难想到虚树。
虚仙人掌的建立可以使用圆方树来实现，可以证明虚圆方树和虚仙人掌是等价的。

我们先用一次Tarjan求点双建立出圆方树，然后套用以前的过程建立虚圆方树。
注意，建立虚圆方树可能会出现两个方点直接相连的情况，这样的情况在处理的时候不方便，不妨在每次加入方点的时候都添加一个圆点（环引出去的点）。
显然虚圆方树的点数还是$O(n)$的。

接下来就和裸的仙人掌求直径一样了，在圆方树上Dp，讨论一下当前点是方点还是圆点即可，如果是方点，用单调队列更新答案。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=300005*2;

struct Edge {
	int from,to;
	LL dist;
};

int n,m,q,root,step,BCC=0,New,Dfn[maxn],Lowlink[maxn],Belong[maxn],First[maxn],Last[maxn],Depth[maxn],p[maxn][25];
LL Length[maxn],f[maxn],Dist[maxn],Dist1[maxn],Dist2[maxn],ans=0;
vector<Edge>edges,edges2[maxn],tree[maxn];
vector<int>G[maxn],Circle[maxn],a;
stack<Edge>S;

void AddEdge(int x,int y,LL v) {
	edges.push_back((Edge) {x,y,v});
	G[x].push_back(edges.size()-1);
}

void AddEdge2(int x,int y,LL v) {
	edges2[x].push_back((Edge) {x,y,v});
}

int LCA(int a,int b) {
	if(Depth[a]<Depth[b])swap(a,b);
	int k=20;
	for(int i=k; i>=0; i--) {
		if(Depth[a]==Depth[b])break;
		if(Depth[a]-(1<<i)>=Depth[b])a=p[a][i];
	}
	if(a==b)return b;
	for(int i=k; i>=0; i--)
		if(~p[a][i]&&p[a][i]!=p[b][i]) {
			a=p[a][i];
			b=p[b][i];
		}
	return p[a][0];
}

int get_son(int Now,int target) {
	for(int i=20; i>=0; i--)
		if(~p[Now][i]&&Depth[p[Now][i]]>Depth[target])Now=p[Now][i];
	return Now;
}

void AddEdge3(int x,int y) {
	if(x>n&&x!=p[y][0]) { //方点连出
		int son=get_son(y,x);
		tree[x].push_back((Edge) {x,son,Dist[son]-Dist[x]});
		x=son;
	}
	if(y>n&&x!=p[y][0]) {
		int fa=p[y][0];
		tree[x].push_back((Edge) {x,fa,Dist[fa]-Dist[x]});
		x=fa;
	}
	if(x!=y)tree[x].push_back((Edge) {x,y,Dist[y]-Dist[x]});
}

bool cmp(int x,int y) {
	return First[x]<First[y];
}

void Tarjan(int Now,int fa) {
	step++;
	Lowlink[Now]=Dfn[Now]=step;
	for(int x:G[Now]) {
		Edge& e=edges[x];
		int Next=e.to;
		if(!Dfn[Next]) {
			S.push((Edge) {
				Now,Next,e.dist
			});
			Tarjan(Next,x);
			Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);
			if(Dfn[Now]<Lowlink[Next])AddEdge2(Now,Next,e.dist),S.pop();
			else if(Dfn[Now]==Lowlink[Next]) { //构成点双连通分量
				BCC++;
				AddEdge2(Now,++New,0);
				while(!S.empty()) {
					int u=S.top().from,v=S.top().to,dist=S.top().dist;
					S.pop();
					Length[BCC]+=dist;
					f[u]=f[v]+dist;
					if(u!=Now) {
						Belong[u]=BCC;
						Circle[New].push_back(u);
					}
					if(u==Now&&v==Next)break;
				}
				for(int i=0; i<Circle[New].size(); i++) {
					int Next=Circle[New][i];
					AddEdge2(New,Next,min(abs(f[Next]-f[Now]),Length[BCC]-abs(f[Next]-f[Now])));
				}
			}
		} else if((x!=(fa^1))&&Lowlink[Now]>Dfn[Next]) {
			Lowlink[Now]=Dfn[Next];
			S.push((Edge) {
				Now,Next,e.dist
			});
		}
	}
}

void Dfs(int Now,int fa,int depth,LL dist) {
	Depth[Now]=depth;
	Dist[Now]=dist;
	First[Now]=++step;
	p[Now][0]=fa;
	for(int i=1; i<=20; i++)
		if(~p[Now][i-1])p[Now][i]=p[p[Now][i-1]][i-1];
		else break;
	for(Edge& e:edges2[Now]) {
		int Next=e.to;
		Dfs(Next,Now,depth+1,dist+e.dist);
	}
	Last[Now]=step;
}

struct Cir {
	int u;
	LL d;
};

void TreeDp(int Now) {
	Dist1[Now]=Dist2[Now]=0;
	for(Edge& e:tree[Now]) {
		int Next=e.to;
		TreeDp(Next);
		if(Dist1[Next]+e.dist>Dist1[Now]) { //所有转移都一样
			Dist2[Now]=Dist1[Now];
			Dist1[Now]=Dist1[Next]+e.dist;
		} else if(Dist1[Next]+e.dist>Dist2[Now])Dist2[Now]=Dist1[Next]+e.dist;
	}
	if(Now>n) { //方点
		deque<int>Q;
		static vector<Cir>tmp;
		tmp.clear();
		Q.clear();
		int NowBlock=Belong[tree[Now][0].to];
		for(Edge& e:tree[Now])tmp.push_back((Cir) {e.to,f[e.to]});
		for(Edge& e:tree[Now])tmp.push_back((Cir) {e.to,f[e.to]+Length[NowBlock]});
		Q.push_back(0);
		for(int i=1; i<tmp.size(); i++) {
			while(!Q.empty()&&tmp[i].d-tmp[Q.front()].d>Length[NowBlock]/2)Q.pop_front();
			if(!Q.empty())ans=max(ans,Dist1[tmp[i].u]+Dist1[tmp[Q.front()].u]+tmp[i].d-tmp[Q.front()].d);
			while(!Q.empty()&&Dist1[tmp[Q.back()].u]-tmp[Q.back()].d<=Dist1[tmp[i].u]-tmp[i].d)Q.pop_back();
			Q.push_back(i);
		}
	} else ans=max(ans,Dist1[Now]+Dist2[Now]);
	tree[Now].clear(); //清空虚树 
}

void build(vector<int>& a) {
	int tmp=a.size();
	for(int i=0; i<tmp-1; i++)a.push_back(LCA(a[i],a[i+1]));
	sort(a.begin(),a.end(),cmp);
	auto it=unique(a.begin(),a.end());
	a.erase(it,a.end());
	static int top=0,S[maxn];
	root=S[++top]=a[0];
	for(int i=1; i<a.size(); i++) {
		int now=a[i];
		while(top>=1) {
			if(First[now]>=First[S[top]]&&First[now]<=Last[S[top]]) {
				AddEdge3(S[top],now);
				break;
			}
			top--;
		}
		if(S[top]!=now)S[++top]=now;
	}
}

int main() {
	int size=40<<20;
	__asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size)); 
	memset(p,-1,sizeof(p));
	New=n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=m; i++) {
		LL x=Get_Int(),y=Get_Int(),v=Get_Int();
		AddEdge(x,y,v);
		AddEdge(y,x,v);
	}
	Tarjan(1,-1);
	step=0;
	Dfs(1,-1,1,0);
	q=Get_Int();
	while(q--) {
		int k=Get_Int();
		a.clear();
		for(int i=1; i<=k; i++)a.push_back(Get_Int());
		sort(a.begin(),a.end(),cmp);
		build(a);
		ans=0;
		TreeDp(root);
		printf("%lld\n",ans);
	}
	exit(0);
}