loj2587「APIO2018」铁人两项

loj2587「APIO2018」铁人两项

​​ 建立圆方树 考虑我们要求解的其实是 圆方树上任意两个圆点之间的路径和

当然方点的点权就是e这个点双包含的点的个数 为了去重圆点的权值就是-1 我们考虑如何计算这样 任意两点的权值和 我们不妨假设 我们枚举每个中间点 然后看他会对多少对圆点产生贡献即可 就在树上跑一下 注意在圆点的时候 因为这个圆点的-1 也会产生贡献 所以每个圆点实际上对于所有的圆点都可以产生贡献 图不连通..

#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while (!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while (isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10,M=2e5+10;struct node{ int y,next;}data[M<<1],data1[M<<1];int h[N],h1[N<<1],cnt,num,w[N<<1],size[N<<1],sum,s;ll ans;int n,m,dfn[N],low[N],q[N],top;inline void insert1(int x,int y){ data1[++cnt].y=y;data1[cnt].next=h1[x];h1[x]=cnt; data1[++cnt].y=x;data1[cnt].next=h1[y];h1[y]=cnt;}inline void dfs(int x,int fa){ dfn[x]=low[x]=++num;q[++top]=x;w[x]=-1;++sum; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa) continue; if (!dfn[y]){ dfs(y,x);low[x]=min(low[x],low[y]); if (low[y]>=dfn[x]){ ++s;++w[s];insert1(x,s);int v; do{ v=q[top--];insert1(s,v);++w[s]; }while(v!=y); } }else low[x]=min(low[x],dfn[y]); }}inline void dfs1(int x,int fa){ size[x]=x<=n; for (int i=h1[x];i;i=data1[i].next){ int y=data1[i].y;if (y==fa) continue; dfs1(y,x);size[x]+=size[y];ans+=(ll)size[y]*w[x]*(sum-size[y]); } ans+=(ll)(sum-size[x])*size[x]*w[x]; if (x<=n) ans+=w[x]*(sum-1);}int main(){ freopen("loj2587.in","r",stdin); n=read();m=read();s=n; for (int i=1;i<=m;++i){ int x=read(),y=read(); data[++num].y=y;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].next=h[y];h[y]=num; }num=0; for (int i=1;i<=n;++i){ sum=0; if (!dfn[i]) dfs(i,i),dfs1(i,i); }printf("%lld\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。