N个点m条边，每个点有一个点权a。 对于任意一个三元环 (i，j，k)（i<j<k） ，它的贡献 为max(ai，aj，ak) 求所有三元环的贡献和。 N<100000，，m<250000。
我们都知道一个定理就是一个图，枚举不比一个点度数小的点只有根号m个。 因此我们可以以度数来定义优先级，度数大优先级高，相同度数编号越大优先级越高。 对于一个三元环，我们希望在它优先最高的点上统计到它。 枚举一条边，设连接了u和v，因为是无向边，注意不要枚举重复，因此这里设u的优先级要比v小。 接下来我们就需要找到所有的w，使得w与u和v都相连且w优先级比u和v都高。 根据定理，这样的w只有根号个，我们直接枚举与u相连的优先级高于u的点，以及与v相连的优先级高于v的点，这里的交集是合法的，就能统计答案。
#include<cstdio> #include<algorithm> #define fo(i,a,b) for(i=a;i<=b;i++) #define max(a,b) (a>b?a:b) using namespace std; typedef long long ll; const int maxn=100000+10,maxm=250000+10; int h[maxn],go[maxm*2],nxt[maxm*2]; int h2[maxn],g2[maxm*2],n2[maxm*2]; int a[maxn],d[maxn]; bool bz[maxn]; int i,j,k,l,r,t,n,m,tot,top,cnt; ll ans; int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x*f; } void add(int x,int y){ d[y]++; go[++tot]=y; nxt[tot]=h[x]; h[x]=tot; } void add2(int x,int y){ g2[++top]=y; n2[top]=h2[x]; h2[x]=top; } bool cmp(int x,int y){ return d[x]<d[y]||d[x]==d[y]&&x<y; } int main(){ n=read();m=read(); fo(i,1,n) a[i]=read(); fo(i,1,m){ j=read();k=read(); add(j,k);add(k,j); } fo(i,1,n){ t=h[i]; while (t){ if (cmp(i,go[t])) add2(i,go[t]); t=nxt[t]; } } fo(i,1,n){ t=h[i]; while (t){ j=go[t]; if (cmp(i,j)){ r=h2[i]; while (r){ bz[g2[r]]=1; r=n2[r]; } r=h2[j]; while (r){ if (bz[g2[r]]==1) ans+=(ll)max(a[i],max(a[j],a[g2[r]])); r=n2[r]; } r=h2[i]; while (r){ bz[g2[r]]=0; r=n2[r]; } } t=nxt[t]; } } printf("%lld\n",ans); }