| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1318775 | exoworldgd | 2017 지구멸망 (FXCUP2_apocalypse) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O5,unroll-loops,inline,fast-math,omit-frame-pointer,tree-vectorize")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=native,fma,abm,mmx,sse")
#include<bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
#define int long long
using namespace std;
const int mod=1e9+7,inf=0x3f3f3f3f,N=3e5+5;
int par[N],sz[N],p2[N],p2i[N],v1[N],v2[N],A,B,C,T,n;
vector<pair<int,pair<int,int>>> e;
int inv(int a,int m){
int x=a,y=m,u=1,v=0;
for(int q;y^1;)q=x/y,x-=q*y,swap(x,y),u-=q*v,swap(u,v);
return (v+m)%m;
}
int ip2(int x){return x>N-5?0:p2i[x];}
int fd(int x){return par[x]=par[x]^x?fd(par[x]):x;}
signed main(void){
exoworldgd;
cin>>n;
for(int i=1,a,b,c;i<=n;i++)cin>>a>>b>>c,e.push_back({c,{a,b}});
sort(e.begin(),e.end()),reverse(e.begin(),e.end()),p2[0]=1,fill(sz,sz+N,1),iota(par,par+N,0),sz[0]=inf;
for(int i=1;i<=n+1;i++)p2[i]=p2[i-1]*2%mod;
for(int i=0;i<=n+1;i++)p2i[i]=inv(p2[i],mod);
for(auto x:e){
int w=x.first,a=fd(x.second.first),b=fd(x.second.second),t=ip2(sz[a])+ip2(sz[b])-ip2(sz[a]+sz[b]);
t%=mod;if(t<0)t+=mod,B=(B+w*((T-v1[a]-v1[b]+mod)%mod*t%mod))%mod,B=(B+w*(((ip2(sz[b])-ip2(sz[a]+sz[b])+mod)%mod*v2[b]+ip2(sz[a])*v1[b])%mod))%mod,B=(B+w*(((ip2(sz[a])-ip2(sz[b]+sz[a])+mod)%mod*v2[a]+ip2(sz[b])*v1[a])%mod))%mod,A=(A+w*t)%mod,C=(C+w*w%mod*t)%mod,T=(T-v1[a]-v1[b]+2*mod)%mod,par[a]=b,sz[b]+=sz[a],v1[b]=(v1[b]+v1[a]+w*t)%mod,T=(T+v1[b])%mod,v2[b]=(v2[b]+v2[a]+w)%mod;
}
A=A*p2[n]%mod,B=B*p2[n]%mod,C=(C*p2[n]%mod+B*2)%mod,cout<<A<<"\n"<<C;
}