学步园

SPOJ 3978 Distance Query

题意：给出一棵有边权的树（100000个点），有100000次讯问两点间路径上的最长边和最短边。

扩展Tarjan算法可以离线解决LCA问题（http://blog.csdn.net/kksleric/article/details/7442258）因此也可用于维护两点间路径上的性质。

设mx[i]为i点到当前集合根节点（tarjan过程中并查集的父亲）路径上的最长边，在合并和路径压缩时根据意义进行相应改变，那么在点a的子树都完成dfs后，所有lca是a的查询<x,y>,其路径上的最长边=MAX{mx[a],mx[b]}.

高效求解次小生成树

普通次小生成树的做法首先最小生成树上每个点为根dfs，求出树上任意两点之间的最长边。然后枚举所有不在最小生成树上的边，将其添加到树上必定形成一个环，去掉环上的最长边形成的生成树最小，由此得出（严格）次小生成树。因此复杂度为O(nlogn+n*n)。利用扩展tarjan，求出所有不在最小生成树中的边
<a,b>之间在最小生成树中路径上的最长边，相当于进行O(n) 次查询，因此复杂度为O(nlogn+n)。

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
struct node {
		int be, ne, val;
		void init(int b, int e, int v) {
			be = b;
			ne = e;
			val = v;
		}
	};
	node buf[200010], query[200010],res[100010];
	int Eb[100010], lb, Eq[100010], lq,Er[100010],lres;
	void addres(int a,int b,int v){
		res[lres].init(b,Er[a],v);
		Er[a]=lres++;
	}
	void addedge(int a, int b, int v) {
		buf[lb].init(b, Eb[a], v);
		Eb[a] = lb++;
		buf[lb].init(a, Eb[b], v);
		Eb[b] = lb++;
	}

	void addquery(int a, int b, int v) {
		query[lq].init(b, Eq[a], v);
		Eq[a] = lq++;
		query[lq].init(a, Eq[b], v);
		Eq[b] = lq++;
	}

	int f[100010], vis[100010];
	int mn[100010],mx[100010],inf=1<<28;
	int  n,ans1[100010],ans2[100010];

	int find(int x) {
		int temp=f[x];
		if (x != temp)
			f[x] = find(f[x]);
		mn[x]=min(mn[x],mn[temp]);
		mx[x]=max(mx[x],mx[temp]);
		return f[x];
	}

	void init() {
		lq = lb =lres=0;
		for (int i = 1; i <= n; i++) {
			f[i] = i;
			Er[i]=Eb[i] = Eq[i] = -1;
		    mx[i]=-inf;
		    mn[i]=inf;
		}
	}

	void dfs(int a) {
		vis[a]=1;
		for (int i = Eq[a]; i != -1; i = query[i].ne) {
			int b = query[i].be;
			if (vis[b] == 1){
				int temp=find(b);
				addres(temp,a,i);
				}
		}
		for (int i = Eb[a]; i != -1; i = buf[i].ne) {
			int b = buf[i].be;
			if (vis[b] == 0){
				dfs(b);
				f[b] =a;
			    mx[b]=mn[b]=buf[i].val;
			}
		}
		for(int i=Er[a];i!=-1;i=res[i].ne){
			int x=res[i].be;
			int t=res[i].val;
			int y=query[t].be;
			find(x);
		    find(y);
			ans1[query[t].val]=min(mn[x], mn[y]);
			ans2[query[t].val]=max(mx[x], mx[y]);
		}
	}
	int main(){
		int m,a,b,v;
		scanf("%d",&n);
		init();
		for(int i=1;i<n;i++)
		{
			scanf("%d%d%d",&a,&b,&v);
			addedge(a,b,v);
		}
		scanf("%d",&m);
		for(int i=0;i<m;i++){
			scanf("%d%d",&a,&b);
			addquery(a,b,i);
		}
		dfs(1);
		for(int i=0;i<m;i++)
			printf("%d %d\n",ans1[i],ans2[i]);
		return 0;
	}