CF915F Imbalance Value of a Tree

2018-09-29 11:01:58

求 $\sum_{j=i}^nF(i,j)$ 　( $n<=1e6$ )

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=1e6+5;
struct E
{
int to,nxt;
}edge[N<<1];
struct node
{
int x,id;
}c[N];
bool vis[N];
ll ans;
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
{
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
bool cmp1(node a,node b){return a.x==b.x?a.id>b.id:a.x<b.x;}
bool cmp2(node a,node b){return a.x==b.x?a.id>b.id:a.x>b.x;}
int main()
{
for (reg int i=1;i<n;i++)
{
}
sort(c+1,c+n+1,cmp1);
for (reg int j=1;j<=n;j++)
{
int k=c[j].id; vis[k]=1;
{
int v=edge[i].to;
if (!vis[v]) continue; v=find(v);
ans+=1ll*c[j].x*tot[k]*tot[v];
f[v]=k; tot[k]+=tot[v];
}
}
sort(c+1,c+n+1,cmp2); memset(vis,0,sizeof(vis));
for (reg int i=1;i<=n;i++) f[i]=i,tot[i]=1;
for (reg int j=1;j<=n;j++)
{
int k=c[j].id; vis[k]=1;
}