「51nod 1743」雪之国度

发表于

雪之国度有 NN 座城市，依次编号为 11 到 NN，又有 MM 条道路连接了其中的城市，每一条道路都连接了不同的 22 个城市，任何两座不同的城市之间可能不止一条道路。

雪之女王赋予了每一座城市不同的能量，其中第 ii 座城市被赋予的能量为 WiW_i 。如果城市 uu 和 vv 之间有一条道路，那么只要此刻雪之女王的能量不小于 ∣Wu−Wv∣|W_u-W_v| ，这条道路就是安全的。如果城市 uu 和 vv 之间存在两条没有重复道路的安全路径（其中每一段道路都是安全的），则认为这两座城市之间有着良好的贸易关系。

最近，雪之女王因为情感问题，她的能量产生巨大的波动。为了维持雪之国度的经济贸易，她希望你能帮忙对 QQ 对城市进行调查。

对于第 jj 对城市 uju_j 和 vjv_j ，她希望知道在保证这两座城市之间有着良好贸易关系的前提之下，自己最少需要保持多少的能量。

Constraints

3≤N≤1000003\leq N\leq 100000 ， 3≤M≤5000003\leq M\leq 500000 ， 1≤Q≤1000001\leq Q\leq 100000 ， 0≤W≤2000000\leq W\leq 200000

Solution

城市间存在两条没有重复道路的安全路径，即两座城市在同一个边双里。题意可以转化为，在保证两个城市在同一个边双联通分量的情况下，求最大边权的最小值。很容易想到一种做法：将边按照边权从小到大加入直到两座城市在同一个边双里。

首先构造出原图的最小生成树，然后考虑按照边权从小到大加入非树边。考虑加进一条非树边会造成的影响：在加入非树边 u−vu-v 时，uu 到 vv 的简单路径上的所有点都会被缩进一个边双联通分量里，这时候我们可以给路径上的所有点打上这条非树边边权的标记，代表这个点与其父亲第一次进入同一个边双时该边双的最大边权。然后利用并查集将路径上的所有点缩成一个点，避免已更新过的点被重复更新。

现在考虑处理询问。利用并查集可以直接判断两个点最后是否在同一个边双里。若在，则答案为 uu 和 vv 路径上的除 lcalca 外节点标记最大值。

具体可以用倍增来实现，时间复杂度 O(nlogn)O(nlogn) 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<cstdio>
#include<algorithm> 
#include<cstring>
#include<cmath>
#include<cstdlib>
#define LL long long
using namespace std;
const int N=1e5+5;
int n,m,Q,cnt,x,y,tot;
int first[N],w[N],f[N];
int deep[N],fa[N][17],v[N][17];
bool ontr[N*5];
struct node{int x,y,v;}a[N*5];
struct edge{int to,next,w;}e[N*2];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
bool cmp(node a,node b){return a.v<b.v;}
void ins(int u,int v,int w){e[++cnt]=(edge){v,first[u],w};first[u]=cnt;} 
int find(int t){return f[t]==t?t:f[t]=find(f[t]);}
void dfs(int x,int last)
{
	for(int i=1;(1<<i)<=deep[x];i++)
		fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==last)continue;
		fa[to][0]=x;v[to][0]=e[i].w;
		deep[to]=deep[x]+1;dfs(to,x);
	}
}
void modify(int &x,int val){v[x][0]=val;f[x]=find(fa[x][0]);x=f[x];}
int tim=0;
int lca(int x,int y)
{
	if(deep[x]<deep[y])swap(x,y);
	int ans=0,d=deep[x]-deep[y];
	for(int i=0;(1<<i)<=d;i++)
		if((1<<i)&d)ans=max(ans,v[x][i]),x=fa[x][i];
	if(x==y)return ans;
	for(int i=16;i>=0;i--)
		if(fa[x][i]!=fa[y][i])
		{
			ans=max(ans,max(v[x][i],v[y][i]));
			x=fa[x][i];y=fa[y][i];
		}
	ans=max(ans,max(v[x][0],v[y][0]));
	return ans;
}
int main()
{
	n=read();m=read();Q=read();
	for(int i=1;i<=n;i++)w[i]=read();
	for(int i=1;i<=m;i++)
	{
		a[i].x=read();a[i].y=read();
		a[i].v=abs(w[a[i].x]-w[a[i].y]);
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++)
	{
		x=find(a[i].x);y=find(a[i].y);
		if(x==y)continue;
		ins(a[i].x,a[i].y,a[i].v);
		ins(a[i].y,a[i].x,a[i].v);
		tot++;ontr[i]=true;f[y]=x;
		if(tot==n-1)break;
	}
	dfs(1,-1);
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++)
	{
		if(ontr[i])continue;
		x=find(a[i].x);y=find(a[i].y);
		if(x==y)continue;
		while(x!=y)
		{
			if(deep[x]>deep[y])modify(x,a[i].v);
			else modify(y,a[i].v);
		}
	}
	for(int j=1;j<=16;j++)
		for(int i=1;i<=n;i++)
			v[i][j]=max(v[i][j-1],v[fa[i][j-1]][j-1]);
	while(Q--)
	{
		x=read();y=read();
		if(find(x)!=find(y))printf("infinitely\n");
		else printf("%d\n",lca(x,y));
	}
	return 0;
}