P5327 [ZJOI2019]语言

(Updated: )
oi

题目链接：P5327

九条可怜是一个喜欢规律的女孩子。按照规律，第二题应该是一道和数据结构有关的题。

在一个遥远的国度，有 $n$ 个城市。城市之间有 $n − 1$ 条双向道路，这些道路保证了任何两个城市之间都能直接或者间接地到达。

在上古时代，这 $n$ 个城市之间处于战争状态。在高度闭塞的环境中，每个城市都发展出了自己的语言。而在王国统一之后，语言不通给王国的发展带来了极大的阻碍。为了改善这种情况，国王下令设计了 $m$ 种通用语，并进行了 $m$ 次语言统一工作。在第 $i$ 次统一工作中，一名大臣从城市 $s_i$ 出发，沿着最短的路径走到了 $t_i$，教会了沿途所有城市（包括 $s_i, t_i$）使用第 $i$ 个通用语。

一旦有了共通的语言，那么城市之间就可以开展贸易活动了。两个城市 $u_i, v_i$ 之间可以开展贸易活动当且仅当存在一种通用语 $L$ 满足 $u_i$ 到 $v_i$ 最短路上的所有城市（包括 $u_i, v_i$），都会使用 $L$。

为了衡量语言统一工作的效果，国王想让你计算有多少对城市 $(u, v)\ (u < v)$，他们之间可以开展贸易活动。

对于 $100%$ 的数据，有 $n,m\leq 10^5$。

Tutorial

不妨考虑枚举一个点 $x$，计算从 $x$ 出发的经过 $x$ 的链的并集大小。

将链 $(u,v)$ 拆成 $(1,u)$ 与 $(1,v)$ 两条链，于是他们的并集就多出来了 $(1,\operatorname{lca}(u,v))$。

容易发现，$\operatorname{lca}$ 到 根节点一段的非法贡献很容易计算减去。于是，我们只需要考虑求若干条从根节点出发的链的并集大小。

于是可以套路地把所有点按照 DFS 序排序，则最后的答案即为所有点的深度减去相邻两点的 $\operatorname{lca}$ 的深度。

而所有点的 $\operatorname{lca}$ 即为 DFS 序的最小与最大点的 $\operatorname{lca}$。

注意到如果对于每个点跑一次，时间复杂度大概是 $O(n^2\log n)$ 的，显然复杂度爆炸。

不妨建一棵以 DFS 序为下标的线段树，每个点储存其深度。

减去相邻两点的 LCA 的深度即在合并时减去左区间最右点与右区见最左点的 LCA 的深度。

求出经过每个点的链，也就相当于对一条链所有经过它的点打上标记，容易想到树上差分。

而统计子树标记和线段树合并即可，时间复杂度 $O(n\log ^2n)$。

如果用 $O(1)$ LCA，可以降掉一个 $\log$。

Solution

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
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
	Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
	Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
	Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
	Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
	Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10,LG=18;
int n,m,f[N][LG+5],dep[N],dfn[N],cnt,rt[N];LL Ans;
I int lca(RI x,RI y){
	RI i;for(dep[x]<dep[y]&&(swap(x,y),0),i=LG;~i;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;for(i=LG;~i;i--) if(f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];return f[x][0];
}
class SegmentTree{
	private:
		#define mid (l+r>>1)
		int ct;struct node{int T,G,l,r,S[2];}T[N*LG<<2];
		I void PU(CI x){
			T[x].G=T[T[x].S[0]].G+T[T[x].S[1]].G-dep[lca(T[T[x].S[0]].r,T[T[x].S[1]].l)];
			T[x].l=T[T[x].S[0]].l?T[T[x].S[0]].l:T[T[x].S[1]].l;
			T[x].r=T[T[x].S[1]].r?T[T[x].S[1]].r:T[T[x].S[0]].r;
		}
	public:
		I void U(int& x,CI p,CI v,CI l=1,CI r=n){
			if(!x&&(x=++ct),l==r) return (T[x].T+=v)?T[x].G=dep[T[x].l=T[x].r=p]:T[x].G=T[x].l=T[x].r=0,void();
			dfn[p]<=mid?U(T[x].S[0],p,v,l,mid):U(T[x].S[1],p,v,mid+1,r),PU(x);
		}
		I void M(int& x,CI y,CI l=1,CI r=n){
			if(!x||!y) return (void)(x+=y);
			if(l==r) return (void)(T[x].T+=T[y].T,T[x].G|=T[y].G,T[x].l|=T[y].l,T[x].r|=T[y].r);
			M(T[x].S[0],T[y].S[0],l,mid),M(T[x].S[1],T[y].S[1],mid+1,r),PU(x);
		}
		I int Q(CI x){return T[x].G-dep[lca(T[x].l,T[x].r)];}
}T;
vector<int> G[N],w[N];
#define pb push_back
I void DFS(CI x=1,CI fa=0){dfn[x]=++cnt,dep[x]=dep[f[x][0]=fa]+1;for(auto i:G[x]) i^fa&&(DFS(i,x),0);}
I void U(CI x,CI y){
	T.U(rt[x],x,1),T.U(rt[x],y,1),T.U(rt[y],x,1),T.U(rt[y],y,1);RI z=lca(x,y);
	w[z].pb(x),w[z].pb(y),f[z][0]&&(w[f[z][0]].pb(x),w[f[z][0]].pb(y),0);
}
I void Q(CI x=1,CI fa=0){
	for(auto i:G[x]) i^fa&&(Q(i,x),T.M(rt[x],rt[i]),0);
	for(auto i:w[x]) T.U(rt[x],i,-1);Ans+=T.Q(rt[x]);
}
int main(){
	RI i,j,x,y;for(read(n,m),i=1;i<n;i++) read(x,y),G[x].pb(y),G[y].pb(x);
	for(DFS(),j=1;j<=LG;j++) for(i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
	for(i=1;i<=m;i++) read(x,y),U(x,y);return Q(),writeln(Ans>>1),0;
}