bzoj 3712 Fiolki

Posted on | Views:

树上求 LCA .

对于第 $i$ 个操作,新建一个点 $p$ ,从 $p$ 向 $a,b$ 连边,之后如果 $b$ 还会参与反应,就用 $p$ 代替.

最后会连成一棵森林,考虑每对会产生沉淀的液体 $c_i,d_i​$ 带来的贡献.

如果它们不在一棵树中,显然没有贡献.否则,这两种液体会在它们的 LCA 处形成沉淀(如果还有剩余).

需要考虑之前发生的反应的影响,将所有反应按照 LCA 深度为第一关键字,优先级为第二关键字排序,模拟即可.

时间复杂度 $O(n\log n+k\log k+k\log n)​$ .

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
99
100
101
102
103
104
105
106
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=4e5+10,K=19;
int ecnt=0,to[MAXN],nx[MAXN],head[MAXN];
int n,m,k,cnt=0,fa[MAXN][K],col[MAXN],dep[MAXN];
void addedge(int u,int v)
{
	fa[v][0]=u;
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
struct Reaction
{
	int x,y,dep,pri;
	bool operator < (const Reaction &rhs) const
	{
		if(dep!=rhs.dep)
			return dep>rhs.dep;
		return pri<rhs.pri;	
	}	
}p[MAXN<<1];
void dfs(int u,int F)
{
	fa[u][0]=F,col[u]=cnt;
	for(int i=1;(1<<i)<=dep[u];++i)
		fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		dep[v]=dep[u]+1;
		dfs(v,u);
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=K-1;i>=0;--i)
		if((1<<i)<=dep[x]-dep[y])
			x=fa[x][i];
	if(x==y)
		return x;
	for(int i=K-1;i>=0;--i)
		if((1<<i)<=dep[x] && fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int g[MAXN],pos[MAXN];
int main()
{
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;++i)
		g[i]=read(),pos[i]=i;
	for(int i=1;i<=m;++i)
	{
		int a=read(),b=read();
		addedge(n+i,pos[a]);
		addedge(n+i,pos[b]);
		pos[a]=pos[b]=n+i;
	}
	for(int i=1;i<=n+m;++i)
		if(!fa[i][0])
		{
			++cnt;
			dfs(i,0);
		}
	cnt=0;
	for(int i=1;i<=k;++i)
	{
		int x=read(),y=read();
		if(col[x]!=col[y])
			continue;
		++cnt;
		p[cnt].x=x,p[cnt].y=y;
		p[cnt].dep=dep[lca(x,y)];
		p[cnt].pri=cnt;
	}
	ll ans=0;
	sort(p+1,p+1+cnt);
	for(int i=1;i<=cnt;++i)
	{
		int x=p[i].x,y=p[i].y;
		int t=min(g[x],g[y]);
		ans+=t;
		g[x]-=t,g[y]-=t;
	}
	cout<<(ans<<1)<<endl;
	return 0;
}