【做題記錄】圖論（馬思博）

A. Dominant Indices

設 \(f_{u,i}\) 表示 \(u\) 子樹中距離 \(u\) 為 \(i\) 的點數(shù)，有 \(f_{u,i}=\sum f_{v,i-1}\)，在轉移過程中維護答案。直接轉移是 \(O(n^2)\) 的，于是需要長鏈剖分優(yōu)化。具體地，每個點繼承長兒子的 DP 數(shù)組，然后再將輕兒子合并上去。使用指針即可，時空復雜度都線性。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e6+5;
int n,dep[maxn],mxd[maxn],des[maxn],len[maxn];
int dp[maxn],*cnt=dp,*f[maxn],ans[maxn];
vector<int> e[maxn];
il void dfs1(int u,int fa){
	mxd[u]=dep[u]=dep[fa]+1;
	for(int v:e[u]){
		if(v==fa){
			continue;
		}
		dfs1(v,u);
		if(mxd[v]>mxd[u]){
			mxd[u]=mxd[v];
			des[u]=v;
		}
	}
}
il void dfs2(int u,int fa){
	if(!f[u]){
		len[u]=mxd[u]-dep[u];
		f[u]=cnt,cnt+=len[u]+1;
	}
	f[u][0]=1,ans[u]=0;
	if(des[u]){
		f[des[u]]=f[u]+1;
		dfs2(des[u],u);
		if(f[u][ans[des[u]]+1]>1){
			ans[u]=ans[des[u]]+1;
		}
	}
	for(int v:e[u]){
		if(v==fa||v==des[u]){
			continue;
		}
		dfs2(v,u);
		for(int i=0;i<=len[v];i++){
			f[u][i+1]+=f[v][i];
			if(f[u][i+1]>f[u][ans[u]]||f[u][i+1]==f[u][ans[u]]&&i+1<ans[u]){
				ans[u]=i+1;
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		e[u].pb(v),e[v].pb(u);
	}
	dfs1(1,0),dfs2(1,0);
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<"\n";
	}
	return 0;
}
}
int main(){return asbt::main();}

B. [國家集訓隊] 墨墨的等式

考慮差分，于是問題變?yōu)?\([0,x]\) 中有多少能被拼出來。設 \(m=\min\{a_i\}\)，那么如果 \(w\) 能被拼出來，\(w+mk\;(k\in\mathbb{N})\) 一定能被拼出來。于是對于每個 \(i<m\)，我們只需求出最小的 \(w\equiv i\pmod{m}\) 使得 \(w\) 能被拼出，則在模 \(m\) 余 \(i\) 的剩余系中的答案就是 \(\lfloor\frac{x-w}{m}\rfloor+1\)（當然前提是 \(w\le x\)）。

考慮建圖，對于 \(i<m\)，連一條 \(i\xrightarrow{a_j}(i+a_j)\bmod m\) 的有向邊。于是從 \(0\) 跑一遍最短路，\(dis_i\) 就是 \(w\)。

這個算法即為同余最短路。

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
#define pii pair<int,int>
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace asbt{
const int maxn=5e5+5,inf=1e9;
int n,m=inf,l,r,a[17],dis[maxn];
bool vis[maxn];
vector<pii> e[maxn];
priority_queue<pii> q;
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>l>>r;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]){
			m=min(m,a[i]);
		}
	}
	for(int i=0;i<m;i++){
		for(int j=1;j<=n;j++){
			e[i].pb(mp((i+a[j])%m,a[j]));
		}
	}
	memset(dis,0x3f,sizeof(dis));
	dis[0]=0,q.push(mp(0,0));
	while(q.size()){
		int u=q.top().sec;
		q.pop();
		if(vis[u]){
			continue;
		}
		vis[u]=1;
		for(pii i:e[u]){
			int v=i.fir,w=i.sec;
			if(!vis[v]&&dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(mp(-dis[v],v));
			}
		}
	}
	int ans=0;
	l--;
	for(int i=0;i<m;i++){
		if(dis[i]<=r){
			ans+=(r-dis[i])/m+1;
		}
		if(dis[i]<=l){
			ans-=(l-dis[i])/m+1;
		}
	}
	cout<<ans;
	return 0;
}
}
signed main(){return asbt::main();}

C. Xor-MST

首先將所有點扔到 01-trie 里。貪心地想，兩個連通塊必然在深度盡可能深的位置合并。對于每個結點，暴力計算它的兩個子樹的最小異或和即可。時間復雜度線性對數(shù)方。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e5+5;
int n,rt=1,tot=1,tr[maxn<<5][2];
ll ans;
il int calc(int p,int q,int d){
	if(d==-1){
		return 0;
	}
	if(tr[p][0]&&tr[p][1]){
		if(tr[q][0]&&tr[q][1]){
			return min(calc(tr[p][0],tr[q][0],d-1),calc(tr[p][1],tr[q][1],d-1));
		}else if(tr[q][0]){
			return calc(tr[p][0],tr[q][0],d-1);
		}else{
			return calc(tr[p][1],tr[q][1],d-1);
		}
	}else if(tr[p][0]){
		if(tr[q][0]&&tr[q][1]){
			return calc(tr[p][0],tr[q][0],d-1);
		}else if(tr[q][0]){
			return calc(tr[p][0],tr[q][0],d-1);
		}else{
			return calc(tr[p][0],tr[q][1],d-1)+(1<<d);
		}
	}else{
		if(tr[q][0]&&tr[q][1]){
			return calc(tr[p][1],tr[q][1],d-1);
		}else if(tr[q][0]){
			return calc(tr[p][1],tr[q][0],d-1)+(1<<d);
		}else{
			return calc(tr[p][1],tr[q][1],d-1);
		}
	}
}
il void solve(int p,int d){
	if(!p){
		return ;
	}
	if(d){
		solve(tr[p][0],d-1);
		solve(tr[p][1],d-1);
	}
	if(tr[p][0]&&tr[p][1]){
		ans+=calc(tr[p][0],tr[p][1],d-1)+(1<<d);
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1,x;i<=n;i++){
		cin>>x;
		int p=rt;
		for(int j=29;~j;j--){
			int t=x>>j&1;
			if(!tr[p][t]){
				tr[p][t]=++tot;
			}
			p=tr[p][t];
		}
	}
	solve(rt,29);
	cout<<ans;
	return 0;
}
}
int main(){return asbt::main();}

D. Kuroni and Antihype

先將原題轉化，每次要加入一個點 \(u\)，若有與之按位與為 \(0\) 的已經(jīng)加入的 \(v\) 則將答案累加 \(a_v\)，否則不累加答案。

令 \(a_{n+1}=0\)，并欽定 \(n+1\) 已經(jīng)加入，于是對于每個點 \(u\) 都有對應的 \(v\)。考慮在 \(u\) 加入時連一條邊 \(u\xleftrightarrow{a_u+a_v}v\)，于是我們所求即為最大生成樹再減去所有點權之和。邊數(shù)很多，顯然不能直接建邊。考慮 \(a_u\operatorname{and} a_v=0\)，于是 \(a_u+a_v=a_u\operatorname{or}a_v\)。考慮從大到小枚舉邊權 \(i\)，再枚舉 \(i\) 的子集 \(j\)，此時所有點權為 \(j\) 的和所有點權為 \(i\oplus j\) 的點可以連邊，用并查集維護即可。時間復雜度 \(O(3^{18}\alpha(n))\)。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=3e5+5,N=(1<<18)-1;
int n,cnt[maxn],fa[maxn];
ll ans;
il int find(int x){
	return x!=fa[x]?fa[x]=find(fa[x]):x;
}
il void merge(int u,int v,int w){
	u=find(u),v=find(v);
	if(u==v){
		return ;
	}
	ans+=(cnt[u]+cnt[v]-1)*1ll*w;
	fa[u]=v,cnt[v]=1;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n,cnt[0]=1;
	for(int i=1,x;i<=n;i++){
		cin>>x,cnt[x]++,ans-=x;
	}
	for(int i=0;i<=N;i++){
		fa[i]=i;
	}
	for(int i=N;i;i--){
		for(int j=i;j;j=(j-1)&i){
			if(cnt[j]&&cnt[i^j]){
				merge(j,i^j,i);
			}
		}
	}
	cout<<ans;
	return 0;
}
}
int main(){return asbt::main();}

E. [BalkanOI 2011] timeismoney

考慮對于每一棵生成樹記一個點 \((\sum a,\sum b)\)，于是所有有可能成為答案的點都在一個下凸包上。證明如下：

如圖，\(A-B-C-D-E\) 組成了一個下凸包，對于其外的 \(F\)，\(OF\) 與 \(A-B-C-D-E\) 的交點 \(G\) 比 \(F\) 優(yōu)。對于過 \(B\) 的反比例函數(shù) \(f\)，其與 \(OF\) 的交點 \(H\) 又比 \(G\) 優(yōu)，而 \(H\) 和 \(B\) 又是等同的，所以最優(yōu)點一定在下凸包 \(A-B-C-D-E\) 上。

根據(jù)這里的證明，凸包上的點數(shù)最多為 \(O((na)^{\frac{2}{3}})\) 個。現(xiàn)在的問題是怎么找到這些點。

首先我們先找到 \(x\) 最小的點 \(A\) 和 \(y\) 最小的點 \(E\)，然后去找凸包上 \(AE\) 這一段中離 \(AE\) 最遠的點 \(B\)。顯然 \(B\) 在 \(AE\) 左側，且 \(B\) 到 \(AE\) 的距離最大，也就是 \(\overrightarrow{AE}\times\overrightarrow{AB}\) 最小。有：

\[\begin{aligned} \overrightarrow{AE}\times\overrightarrow{AB}&=(x_E-x_A)(y_B-y_A)-(y_E-y_A)(x_B-x_A)\\ &=(x_E-x_A)y_B+(y_A-y_E)x_B+x_Ay_E-x_Ey_A \end{aligned} \]

于是我們最小化 \((x_E-x_A)y_B+(y_A-y_E)x_B\) 即可，將邊權設為 \((x_E-x_A)b+(y_A-y_E)a\) 跑 kurskal 就好了。然后遞歸 \(AB\) 和 \(BE\) 即可。時間復雜度 \(O((na)^{\frac{2}{3}}m\log m)\)。

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e4+5;
int n,m,fa[205];
struct edge{
	int u,v,a,b,w;
	il bool operator<(const edge &x)const{
		return w<x.w;
	}
}a[maxn];
struct node{
	int x,y;
	node(int x=0,int y=0):x(x),y(y){}
	il node operator-(const node &b)const{
		return node(x-b.x,y-b.y);
	}
	il int operator*(const node &b)const{
		return x*b.y-y*b.x;
	}
	il bool operator<(const node &b)const{
		return x*y<b.x*b.y||x*y==b.x*b.y&&x<b.x;
	}
}ans;
il int find(int x){
	return x!=fa[x]?fa[x]=find(fa[x]):x;
}
il node mst(){
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	sort(a+1,a+m+1);
	int x=0,y=0;
	for(int i=1,u,v;i<=m;i++){
		u=find(a[i].u),v=find(a[i].v);
		if(u!=v){
			fa[u]=v;
			x+=a[i].a,y+=a[i].b;
		}
	}
	return node(x,y);
}
il void solve(node A,node B){
	for(int i=1;i<=m;i++){
		a[i].w=(B.x-A.x)*a[i].b+(A.y-B.y)*a[i].a;
	}
	node C=mst();
	if((B-A)*(C-A)==0){
		return ;
	}
	ans=min(ans,C);
	solve(A,C),solve(C,B);
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].u>>a[i].v>>a[i].a>>a[i].b;
		a[i].u++,a[i].v++;
	}
	for(int i=1;i<=m;i++){
		a[i].w=a[i].a;
	}
	node A=mst();
	for(int i=1;i<=m;i++){
		a[i].w=a[i].b;
	}
	node B=mst();
	ans=min(A,B);
	solve(A,B);
	cout<<ans.x<<' '<<ans.y;
	return 0;
}
}
signed main(){return asbt::main();}

M. [POI 2014] HOT-Hotels 加強版

首先考慮合法的 \((i,j,k)\) 的形態(tài)，可以想到這樣兩種：

可以想到設 \(f_{u,i}\) 表示 \(u\) 子樹中距離 \(u\) 為 \(i\) 的點的個數(shù)，長剖優(yōu)化是顯然的，但是優(yōu)化后難以直接計算第二種情況。于是再設 \(g_{u,i}\) 表示 \(u\) 子樹內滿足 \(\operatorname{dis}(\operatorname{lca}(x,y),x)=\operatorname{dis}(\operatorname{lca}(x,y),y)=\operatorname{dis}(\operatorname{lca}(x,y),u)+i\) 的 \((x,y)\) 的數(shù)量，于是有轉移：\(g_{u,i}=\sum\limits_{v}g_{v,i+1}+\sum\limits_{x,y}f_{x,i-1}\times f_{y,i-1}\)。于是長剖優(yōu)化即可，時空都線性，注意 \(g\) 數(shù)組要開兩倍。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,mxd[maxn],dep[maxn],des[maxn],len[maxn];
int F[maxn],*cf=F,*f[maxn];
ll G[maxn<<1],*cg=G,*g[maxn],ans;
vector<int> e[maxn];
il void dfs1(int u,int fa){
	mxd[u]=dep[u]=dep[fa]+1;
	for(int v:e[u]){
		if(v==fa){
			continue;
		}
		dfs1(v,u);
		if(mxd[u]<mxd[v]){
			mxd[u]=mxd[v],des[u]=v;
		}
	}
}
il void dfs2(int u,int fa){
	if(!f[u]){
		len[u]=mxd[u]-dep[u]+1;
		f[u]=cf,cf+=len[u];
		g[u]=cg+len[u],cg+=len[u]<<1;
	}
	f[u][0]=1;
	if(des[u]){
		int v=des[u];
		f[v]=f[u]+1,g[v]=g[u]-1;
		dfs2(v,u);
	}
	ans+=g[u][0];
	for(int v:e[u]){
		if(v==fa||v==des[u]){
			continue;
		}
		dfs2(v,u);
		for(int i=0;i<len[v];i++){
			if(i){
				ans+=g[v][i]*f[u][i-1];
			}
			ans+=f[v][i]*g[u][i+1];
		}
		for(int i=0;i<len[v];i++){
			if(i){
				g[u][i-1]+=g[v][i];
			}
			g[u][i+1]+=f[u][i+1]*1ll*f[v][i];
			f[u][i+1]+=f[v][i];
		}
	}
//	cout<<u<<":\n";
//	for(int i=0;i<len[u];i++){
//		cout<<f[u][i]<<' ';
//	}
//	cout<<'\n';
//	for(int i=0;i<len[u];i++){
//		cout<<g[u][i]<<' ';
//	}
//	cout<<'\n';
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		e[u].pb(v),e[v].pb(u);
	}
	dfs1(1,0),dfs2(1,0);
	cout<<ans;
	return 0;
}
}
int main(){return asbt::main();}

O. [agc057_d]Sum Avoidance

比較復雜。

Theorem 1：題目所求的 \(A\) 滿足 \(|A|=\lfloor\frac{S-1}{2}\rfloor\)。

Proof 1：

Lemma A：\(|A|\le\lfloor\frac{S-1}{2}\rfloor\)。

Proof A：考慮 \(1\) 到 \(S-1\) 共 \(S-1\) 個數(shù)。根據(jù)鴿巢原理，若 \(|A|>\lfloor\frac{S-1}{2}\rfloor\) 那么必然存在 \(v\) 使得 \(v\) 和 \(S-v\) 被同時選入，矛盾。

于是考慮后 \(\lfloor\frac{S-1}{2}\rfloor\) 個數(shù)，它們兩兩之和都大于 \(S\)。于是得證。

考慮設 \(A\) 中 \(\le\lfloor\frac{S-1}{2}\rfloor\) 的數(shù)組成的集合為 \(B\)，于是我們可以在知道 \(B\) 的情況下還原 \(A\)。

Theorem 2：若 \(a,b\in B,a+b\le\lfloor\frac{S-1}{2}\rfloor\)，那么 \(a+b\in B\)。

Proof 2：若 \(a+b\notin B\)，那么由 Theorem 1 必有 \(S-a-b\in A\)，于是 \(A\) 不合法。

Theorem 3：若 \(B\) 合法，則 \(A\) 合法。

Proof 3：若 \(A\) 不合法，則在 \(A\) 中必然存在 \(x>\lfloor\frac{S-1}{2}\rfloor\) 且能與 \(B\) 中若干個數(shù)組成 \(S\)。換句話說，\(S-x\notin B\) 并且 \(B\) 中若干個數(shù)可以組成 \(S-x\)，與 Theorem 2 矛盾。

那么考慮最小化 \(B\) 的字典序即可。一個顯然的貪心是從小到大枚舉每一個數(shù)，如果加入后合法便加入。考慮第一個被加進去的數(shù) \(d\)，它滿足 \(\operatorname{lcm}(1,2,\dots,d-1)|S\)。發(fā)現(xiàn) \(d\le43\)。

于是對于每個被加進去的數(shù)，分兩類：

能被 \(B\) 中的數(shù)表示，于是必須加入。
不能被表示，但是加入后仍然合法，于是加入。

從模 \(d\) 的剩余系考慮，若 \(x\) 以第二種方式被加入，則必然與 \(B\) 中現(xiàn)有的數(shù)不同余。因此至多有 \(d\) 個數(shù)以第二種方式加入。

考慮怎么快速地維護 \(B\)。考慮一個類同余最短路狀物，設 \(f_i\) 表示能表示出的模 \(d\) 等于 \(i\) 的數(shù)的最小值。于是我們得到 \(f\) 就可還原出 \(B\)，這將在后面說明。

考慮加入數(shù)對 \(f\) 的影響。第一種方式不會影響 \(B\)，而第二種方式會影響。具體地，\(\forall x\in[0,d),i\in[1,d),f_{(x+iv)\bmod d}\leftarrow f_x+iv\)。

考慮求出 \(v\)。首先需要滿足 \(v<f_{v\bmod d}\)，然后需要滿足用 \(v\) 更新后 \(f_{S\bmod d}>S\)。枚舉 \(x=v\bmod d\)，于是可以求出 \(v\) 的下界：

\[v_x=\max_{i=1}^{d-1}\lfloor\frac{S-f_{(S-iv)\bmod d}}{i}\rfloor+1 \]

于是 \(v=\min v_x\)，再用 \(v\) 更新 \(f\) 即可。這一部分時間復雜度 \(O(d^3)\)。

考慮用 \(f\) 數(shù)組求答案。對于 \(x\le\lfloor\frac{S-1}{2}\rfloor\)，可以求出 \(B\) 中 \(\le x\) 的數(shù)的數(shù)量：

\[\sum_{i=0}^{d-1}\lfloor\frac{x-f_i}w0obha2h00\rfloor+[i\ne0] \]

于是二分即可。這一部分時間復雜度 \(O(d\log S)\)。

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int inf=2e18;
int T,S,K,d,f[49];
il int count(int x){
	int cnt=0;
	for(int i=0;i<d;i++){
		if(x>=f[i]){
			cnt+=(x-f[i])/d+(i>0);
		}
	}
	return cnt;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--){
		cin>>S>>K;
		if(K>(S-1)>>1){
			cout<<-1<<'\n';
			continue;
		}
		d=1;
		while(S%d==0){
			d++;
		}
		memset(f,0x3f,sizeof(f));
		f[0]=0;
		while(1){
			int v=inf;
			for(int i=1;i<d;i++){
				int t=0;
				for(int j=1;j<d;j++){
					t=max(t,(S-f[((S-i*j)%d+d)%d])/j+1);
				}
				while(t%d!=i){
					t++;
				}
				if(t<f[i]){
					v=min(v,t);
				}
			}
			if(v>(S-1)>>1){
				break;
			}
			for(int i=0;i<d;i++){
				int t=i;
				do{
					int x=(t+v)%d;
					f[x]=min(f[x],f[t]+v);
					t=x;
				}while(t!=i);
			}
		}
		if(count((S-1)>>1)>=K){
			int l=1,r=(S-1)>>1;
			while(l<r){
				int mid=(l+r)>>1;
				if(count(mid)>=K){
					r=mid;
				}
				else{
					l=mid+1;
				}
			}
			cout<<l<<'\n';
		}else{
			int l=S-(S-1)/2,r=S-1;
			while(l<r){
				int mid=(l+r)>>1;
				if((S-1)/2-(S-mid-1-count(S-mid-1))>=K){
					r=mid;
				}
				else{
					l=mid+1;
				}
			}
			cout<<l<<'\n';
		}
	}
	return 0;
}
}
signed main(){return asbt::main();}

P. Team Players

考慮容斥。設至少有 \(0\) 條連邊的三元組的貢獻和為 \(c0\)，類似地有 \(c1,c2,c3\)，于是答案為 \(c0-c1+c2-c3\)。

對于 \(c0\)，考慮每個 \(u\) 的貢獻，即考慮另外兩個數(shù)與 \(u\) 的大小關系。于是貢獻為：\(c{u\choose2}+bu(n-u-1)+a{n-u-1\choose2}\)。

對于 \(c1\)，枚舉每一條邊 \((u,v)\)，不妨令 \(u<v\)，考慮第三個數(shù) \(t\) 與 \(u,v\) 的關系即可。

對于 \(c2\)，考慮枚舉每個點的出邊。對于 \(u\) 的所有出邊 \((u,v)\)，假設 \(v\) 的排名是 \(i\)（從 \(0\) 開始），于是 \(v\) 的貢獻可以分兩類討論：

\(v>u\)，貢獻為 \(ivc+(d_u-i-1)vb\)。
\(v<u\)，貢獻為 \(ivb+(d_u-i-1)va\)。

而 \(u\) 的貢獻，假設有 \(l\) 個點比 \(u\) 小，\(r\) 個點比 \(u\) 大，于是貢獻為 \(cu{l\choose2}+lrub+au{r\choose2}\)。

對于 \(c3\)，其實質是一個三元環(huán)計數(shù)。考慮將無向圖轉為有向圖，每條邊指向度數(shù)更大的那一個點，于是每個點的出度顯然 \(\le\sqrt{m}\)。此時再枚舉每一條邊 \((u,v)\)，求出 \(u\) 和 \(v\) 能共同到的點即可。

總時間復雜度 \(O(n+m+m\log m+m\sqrt{m})\)。

Code

#include<bits/stdc++.h>
#define int unsigned long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=2e5+5;
int n,m,a,b,c,d[maxn];
bool vis[maxn];
vector<int> e[maxn];
struct{
	int u,v;
}E[maxn];
il int calc0(){
	int res=0;
	for(int i=0;i<n;i++){
		res+=(n-i-1)*(n-i-2)/2*a*i;
		res+=i*(n-i-1)*b*i;
		res+=i*(i-1)/2*c*i;
	}
//	cout<<0<<' '<<res<<'\n';
	return res;
}
il int calc1(){
	int res=0;
	for(int i=1;i<=m;i++){
		int u=E[i].u,v=E[i].v;
		res+=u*(u-1)/2*a+u*u*b+v*u*c;
		res+=u*(v-u-1)*a+(u+v)*(v-u-1)/2*b+v*(v-u-1)*c;
		res+=u*(n-v-1)*a+v*(n-v-1)*b+(v+n)*(n-v-1)/2*c;
	}
//	cout<<1<<' '<<res<<'\n';
	return res;
}
il int calc2(){
	int res=0;
	for(int u=0;u<n;u++){
		sort(e[u].begin(),e[u].end());
		int l=0,r=d[u];
		for(int i=0;i<d[u];i++){
			int v=e[u][i];
			if(v<u){
				l++,r--;
			}
			if(u<v){
				res+=i*v*c+(d[u]-i-1)*v*b;
			}else{
				res+=i*v*b+(d[u]-i-1)*v*a;
			}
		}
		res+=l*(l-1)/2*u*c+l*r*u*b+r*(r-1)/2*u*a;
	}
//	cout<<2<<' '<<res<<'\n';
	return res;
}
il int calc3(){
	for(int u=0;u<n;u++){
		e[u].clear();
	}
	for(int i=1;i<=m;i++){
		int u=E[i].u,v=E[i].v;
		if(d[u]<d[v]||d[u]==d[v]&&u<v);
		else{
			swap(u,v);
		}
		e[u].pb(v);
	}
	int res=0;
	for(int u=0;u<n;u++){
		for(int v:e[u]){
			vis[v]=1;
		}
		for(int v:e[u]){
			for(int x:e[v]){
				if(vis[x]){
					int hp[3]={u,v,x};
					sort(hp,hp+3);
					res+=a*hp[0]+b*hp[1]+c*hp[2];
				}
			}
		}
		for(int v:e[u]){
			vis[v]=0;
		}
	}
//	cout<<3<<' '<<res<<'\n';
	return res;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>a>>b>>c;
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		if(u>v){
			swap(u,v);
		}
		E[i]={u,v},d[u]++,d[v]++;
		e[u].pb(v);
		e[v].pb(u);
	}
//	cout<<calc0()<<' '<<calc1()<<' '<<calc2()<<' '<<calc3();
	cout<<calc0()-calc1()+calc2()-calc3();
	return 0;
}
}
signed main(){return asbt::main();}

posted @ 2025-08-16 10:49 zhangxy__hp 閱讀(16) 評論(0) 收藏舉報

刷新頁面返回頂部

zhangxyhp

【做題記錄】圖論（馬思博）

A. Dominant Indices

B. [國家集訓隊] 墨墨的等式

C. Xor-MST

D. Kuroni and Antihype

E. [BalkanOI 2011] timeismoney

M. [POI 2014] HOT-Hotels 加強版

O. [agc057_d]Sum Avoidance

P. Team Players