CF985G

发表于 分类于
Team Players

Team Players

反向建图不行，直接考虑容斥。

考虑算出来总贡献，然后分别减掉有一条边的贡献，两条边的贡献，三条边的贡献。

当然如果你喜欢可以作二项式反演，但是完全没有必要，毕竟直接算恰好时的贡献更简单。。。

考虑计算总贡献，枚举每个点，分讨其贡献为 $A$ 时的贡献总值，为 $B$ 时的贡献总值，为 $C$ 时的贡献总值。

考虑计算有一条边的贡献。枚举每一条边，然后计算包含这条边的三元组的贡献总和。但这个贡献既不是恰好有一条边的总贡献，也不是至少有一条边的总贡献，而是一条边算一次，两条边算两次，三条边算三次的总贡献。考虑后面容斥掉。

考虑计算有两条边的贡献。枚举中间点，然后找它的出点，组合一下得到找到的三元组的贡献。然而这样得到贡献既不是恰有两条边的贡献，也不是至少两条边的贡献，而是两条边算一次，三条边算三次的贡献。我们仍然考虑容斥掉。

考虑计算有三条边的贡献。直接三元环计数。

然后恰好有两条边的贡献可以很轻松的容斥出来。

然后恰好有一条边的贡献也可以很轻松地容斥出来。

然后答案就能很轻松的容斥出来。

然而我写的复杂度是玄学复杂度（理论上跑不过），算一下大概是 $O( n ^ 2 \log n + m \sqrt{ m })$。

但很显然没有这么多人会想着如何造 G 题的巨大 Hack 数据，所以就水过了。。。

代码：

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
}using Ehnaev::read;

const ll N=2e5;

ll n,m,a[3],tot,A,B,C;
ll ver[N*2+5],head[N+5],nxt[N*2+5];
ll u[N+5],v[N+5],flg[N+5],deg[N+5];
ll buf_more[N+5],buf_less[N+5];

inline unsigned ll C2(ll n) {return n*(n-1)/2;}

inline void Addedge(ll u,ll v) {
  ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

int main() {

  n=read();m=read();A=read();B=read();C=read();

  unsigned ll tmp0=0;
  for(ll i=0;i<n;i++) {
    tmp0+=A*i*C2(n-i-1);tmp0+=C*i*C2(i);tmp0+=B*i*i*(n-i-1);
  }

  unsigned ll tmp1=0;
  for(ll i=1;i<=m;i++) {
    u[i]=read();v[i]=read();deg[u[i]]++;deg[v[i]]++;
    if(u[i]<v[i]) swap(u[i],v[i]);
    tmp1+=(v[i]*B+u[i]*C)*v[i]+A*C2(v[i]);
    tmp1+=(v[i]*A+u[i]*C)*(u[i]-v[i]-1)+B*(C2(u[i])-C2(v[i]+1));
    tmp1+=(v[i]*A+u[i]*B)*(n-u[i]-1)+C*(C2(n)-C2(u[i]+1));
    Addedge(u[i],v[i]);Addedge(v[i],u[i]);
  }

  unsigned ll tmp2=0;
  for(ll w=0;w<n;w++) {
    ll cnt_more=0,cnt_less=0;
    for(ll i=head[w];i;i=nxt[i]) {
      if(ver[i]>w) {
        cnt_more++;buf_more[cnt_more]=ver[i];
      }
      if(ver[i]<w) {
        cnt_less++;buf_less[cnt_less]=ver[i];
      }
    }
    tmp2+=w*A*C2(cnt_more);
    tmp2+=w*B*cnt_more*cnt_less;
    tmp2+=w*C*C2(cnt_less);
    sort(buf_more+1,buf_more+cnt_more+1);
    sort(buf_less+1,buf_less+cnt_less+1);
    for(ll i=1;i<=cnt_more;i++) {
      tmp2+=buf_more[i]*C*(i-1+cnt_less);
      tmp2+=buf_more[i]*B*(cnt_more-i);
    }
    for(ll i=1;i<=cnt_less;i++) {
      tmp2+=buf_less[i]*A*(cnt_less-i+cnt_more);
      tmp2+=buf_less[i]*B*(i-1);
    }
  }

  for(ll i=1;i<=tot;i++) ver[i]=nxt[i]=0;
  for(ll i=0;i<n;i++) head[i]=0;
  tot=0;

  for(ll i=1;i<=m;i++) {
    if(deg[v[i]]>deg[u[i]]) Addedge(v[i],u[i]);
    else Addedge(u[i],v[i]);
  }

  unsigned ll tmp3=0;
  for(ll w=0;w<n;w++) {
    for(ll i=head[w];i;i=nxt[i]) flg[ver[i]]=1;
    for(ll i=head[w];i;i=nxt[i]) {
      for(ll j=head[ver[i]];j;j=nxt[j]) {
        if(flg[ver[j]]) {
          a[0]=w;a[1]=ver[i];a[2]=ver[j];sort(a,a+3);
          tmp3+=a[0]*A+a[1]*B+a[2]*C;
        }
      }
    }
    for(ll i=head[w];i;i=nxt[i]) flg[ver[i]]=0;
  }

  unsigned ll ans=0;
  tmp2-=tmp3*3;
  tmp1-=tmp2*2+tmp3*3;
  ans=tmp0-tmp1-tmp2-tmp3;

  printf("%llu",ans);

  return 0;
}