[BZOJ5463] [APIO2018] 铁人两项

题目链接

LOJ.

BZOJ.

Solution

先建圆方树。

我们考虑暴力，枚举一个点对，我们枚举的点都是圆点，然后统计中间那个点可以取的位置的数量，加起来就是答案。

那么怎么统计呢，我们对于每个点赋一个点权，方点点权为点双的大小，圆点点权为\(-1\)。

那么这条路径的点权和就是答案，注意要统计到端点的权值。

然后优化就很显然了，直接枚举每个点被算了多少次就行了，这个随便算一下就好了。

复杂度\(O(n)\)。

#include<bits/stdc++.h>

using namespace std;

#define int long long 

void read(int &x) {

    x=0;int f=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;

    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;

}

void print(int x) {

    if(x<0) putchar('-'),x=-x;

    if(!x) return ;print(x/10),putchar(x%10+48);

}

void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double

#define ll long long 

const int maxn = 4e5+10;

const int inf = 1e9;

const lf eps = 1e-8;

int cnt,n,m,val[maxn],ans,rt;

struct Tree {

	int head[maxn],tot,vis[maxn],sz[maxn];

	struct edge{int to,nxt;}e[maxn<<1];

	void add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}

	void ins(int u,int v) {add(u,v),add(v,u);}

	void dfs(int x,int fa) {

		vis[x]=1,sz[x]=x<=n;

		for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) dfs(e[i].to,x),sz[x]+=sz[e[i].to];

	}

	void solve(int x,int fa) {

		int res=0,s=0;

		for(int i=head[x];i;i=e[i].nxt)

			if(e[i].to!=fa) res+=s*sz[e[i].to],s+=sz[e[i].to];

		res+=s*(sz[rt]-sz[x]);res<<=1;ans+=res*val[x];

		for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) solve(e[i].to,x);

	}

}T;

struct Graph {

	int head[maxn],tot,dfn[maxn],low[maxn],dfn_cnt,sta[maxn],top;

	struct edge{int to,nxt;}e[maxn<<1];

	void add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}

	void ins(int u,int v) {add(u,v),add(v,u);}

	void tarjan(int x,int fa) {

		dfn[x]=low[x]=++dfn_cnt,sta[++top]=x;

		for(int v,i=head[x];i;i=e[i].nxt) {

			if((v=e[i].to)==fa) continue;

			if(!dfn[v]) tarjan(v,x),low[x]=min(low[x],low[v]);

			else {low[x]=min(low[x],dfn[v]);continue;}

			if(low[v]>=dfn[x]) {

				++cnt;T.ins(cnt,x);val[cnt]++;

				while(top) {

					int now=sta[top--];T.ins(now,cnt),val[cnt]++;

					if(now==v) break;

				}

			}

		}

	}

}G;

signed main() {

	read(n),read(m);for(int i=1,x,y;i<=m;i++) read(x),read(y),G.ins(x,y);

	cnt=n;for(int i=1;i<=n;i++) if(!G.dfn[i]) G.tarjan(i,0);

	for(int i=1;i<=n;i++) val[i]=-1;

	for(int i=1;i<=n;i++) if(!T.vis[i]) rt=i,T.dfs(i,0),T.solve(i,0),ans-=T.sz[i]*(T.sz[i]-1)*2;

	write(ans);

	return 0;

}

巴特西

[BZOJ5463] [APIO2018] 铁人两项

题目链接

Solution

最新文章

热门文章