铁人两项

圆方树入门

题目链接

转化一下题意,等价于求$\sum\limits_x\sum\limits_y S_{x,y}$

$S_{x,y}$表示$x$到$y$的所有不经过重复点的路径可能经过的点的个数

建出圆方树,方点权值为点双大小,圆点权值为$-1$,问题就变成了求树上所有圆点对的路径长度之和

路径长度定义为树上两点路径经过点的权值和(包含这两点)。

每个点的贡献就是经过它的路径数$×$它的权值

注意:图不一定联通

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#define rep(x,a,b) for (int x=int(a);x<=(int)(b);x++)
#define drp(x,a,b) for (int x=int(a);x>=(int)(b);x--)
#define cross(x,a) for (int x=hd[a];x;x=nx[x])
#define ll long long
using namespace std;
inline ll rd()
{
ll _x=0;int _ch=getchar(),_f=1;
for(;!isdigit(_ch)&&(_ch!='-')&&(_ch!=EOF);_ch=getchar());
if (_ch=='-'){_f=0;_ch=getchar();}
for(;isdigit(_ch);_ch=getchar()) _x=_x*10+_ch-'0';
return _f?_x:-_x;
}
void write(ll _x){if (_x>=10) write(_x/10),putchar(_x%10+'0'); else putchar(_x+'0'); }
inline void wrt(ll _x,char _p){if (_x<0) putchar('-'),_x=-_x; write(_x); if (_p) putchar(_p);}
#define maxn 600005
#define maxm 600005
int tot,n,m;
namespace Tree
{
int nx[maxn<<1],to[maxn<<1],hd[maxn<<1],cnt;
inline void add(int u,int v){nx[++cnt]=hd[u],to[cnt]=v,hd[u]=cnt;}
int g[maxn<<1],mx;
ll ans;
int dfs(int u,int fa) {
int sum=u<=n;
cross(i,u) if (to[i]!=fa) {
int x=dfs(to[i],u);
ans+=2ll*g[u]*x*sum;
sum+=x;
}
ans+=2ll*g[u]*sum*(mx-sum);
return sum;
}
}
int dfn[maxn],low[maxn],id;
int sta[maxn],top;
int nx[maxm],to[maxm],hd[maxn],cnt;
inline void add(int u,int v){nx[++cnt]=hd[u],to[cnt]=v,hd[u]=cnt;}
void tarjan(int u,int fa) {
Tree::mx++;
dfn[u]=low[u]=++id;
sta[++top]=u;
for(int i=hd[u];i;i=nx[i]) if (to[i]!=fa) {
int v=to[i];
if (!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if (low[v]>=dfn[u]) { //对于一般图,此处为>=;对于仙人掌,此处为==
tot++;Tree::g[n+tot]=2;
while(sta[top]!=v)
Tree::g[n+tot]++,Tree::add(n+tot,sta[top--]);
Tree::add(n+tot,sta[top--]);
Tree::add(u,n+tot);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
void init(int n)
{
rep(i,1,n) Tree::g[i]=-1;
rep(i,1,n) if (!dfn[i]) {
Tree::mx=0;
tarjan(i,0),Tree::dfs(i,0);
}
}
int main()
{
n=rd(),m=rd();
rep(i,1,m) {
int x=rd(),y=rd();
add(x,y),add(y,x);
}
init(n);
wrt(Tree::ans,'\n');
}
avatar
小C的独立集