jzoj5365 【GDOI2018模拟9.14】通信 線段樹合并

Description

給定一棵樹，求 ∑ i = 1 n ∑ j = i n d i s ( i , j ) + ∑ k = i + 1 j d i s ( k − 1 , k ) ( n 2 ) \dfrac{\sum\limits_{i=1}^n\sum\limits_{j=i}^n{dis(i,j)+\sum\limits_{k=i+1}^j{dis(k-1,k)}}}{\binom{n}{2}} (2n​)i=1∑n​j=i∑n​dis(i,j)+k=i+1∑j​dis(k−1,k)​

n ≤ 1 0 5 n\le 10^5 n≤105

Solution

惡補計數題

一個比較顯然的做法就是我們暴力建虛樹，答案就是虛樹上所有邊的和

我們枚舉每條邊算貢獻，也就是連續一段在兩棵子樹内都出現的方案數。一個比較巧妙地做法就是将其中一棵子樹中的節點在原序列中染黑，那麼連續一段同色的不可能成為答案，我們用總的子區間數量減去同色的子區間數量即可，這樣n^2做就有60分

考慮用線段樹維護同色的長度，我們dfs的時候合并兩顆線段樹并插入目前節點就可以直接做了。當然啟發式合并也是資瓷的

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)

typedef long long LL;
const int MOD=1000000007;
const int ny2=500000004;
const int N=200005;

struct edge {int x,y,next;} e[N];
struct treeNode {int l,r,l0,r0,l1,r1; LL sum;} t[N*51];

int rt[N],ls[N],edCnt,tot,n;

LL ans;

int read() {
	int x=0,v=1; char ch=getchar();
	for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
	for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
	return x*v;
}

void add_edge(int x,int y) {
	e[++edCnt]=(edge) {x,y,ls[x]}; ls[x]=edCnt;
	e[++edCnt]=(edge) {y,x,ls[y]}; ls[y]=edCnt;
}

LL f(LL x) {
	return x*(x+1)%MOD*ny2%MOD;
}

void push_up(int x,int tl,int tr) {
	int ls=t[x].l,rs=t[x].r,mid=(tl+tr)>>1;
	if (!ls) {
		ls=t[x].l=++tot;
		t[ls].l1=t[ls].r1=0;
		t[ls].l0=t[ls].r0=mid-tl+1;
		t[ls].sum=f(mid-tl+1);
	}
	if (!rs) {
		rs=t[x].r=++tot;
		t[rs].l1=t[rs].r1=0;
		t[rs].l0=t[rs].r0=tr-mid;
		t[rs].sum=f(tr-mid);
	}
	t[x].sum=t[ls].sum+t[rs].sum;
	if (t[ls].r0&&t[rs].l0) {
		t[x].sum-=f(t[ls].r0)+f(t[rs].l0);
		t[x].sum+=f(t[ls].r0+t[rs].l0);
	}
	if (t[ls].r1&&t[rs].l1) {
		t[x].sum-=f(t[ls].r1)+f(t[rs].l1);
		t[x].sum+=f(t[ls].r1+t[rs].l1);
	}
	t[x].l0=t[ls].l0+((t[ls].l0==mid-tl+1)?(t[rs].l0):0);
	t[x].l1=t[ls].l1+((t[ls].l1==mid-tl+1)?(t[rs].l1):0);
	t[x].r0=t[rs].r0+((t[rs].r0==tr-mid)?(t[ls].r0):0);
	t[x].r1=t[rs].r1+((t[rs].r1==tr-mid)?(t[ls].r1):0);
}

void ins(int &now,int tl,int tr,int x) {
	if (!now) now=++tot;
	if (tl==tr) {
		t[now].sum=t[now].l1=t[now].r1=1;
		t[now].l0=t[now].r0=0;
		return ;
	}
	int mid=(tl+tr)>>1;
	if (x<=mid) ins(t[now].l,tl,mid,x);
	else ins(t[now].r,mid+1,tr,x);
	push_up(now,tl,tr);
}

int merge(int x,int y,int tl,int tr) {
	if (!(x*y)) return x+y;
	int mid=(tl+tr)>>1;
	if (t[x].l0==tr-tl+1) return y;
	if (t[y].l0==tr-tl+1) return x;
	t[x].l=merge(t[x].l,t[y].l,tl,mid);
	t[x].r=merge(t[x].r,t[y].r,mid+1,tr);
	push_up(x,tl,tr);
	return x;
}

void solve(int x,int from) {
	for (int i=ls[x];i;i=e[i].next) {
		if (e[i].y==from) continue;
		solve(e[i].y,x);
		rt[x]=merge(rt[x],rt[e[i].y],1,n);
	}
	ins(rt[x],1,n,x);
	ans=(ans+MOD+(f(n)-t[rt[x]].sum)*2LL%MOD)%MOD;
}

LL ksm(LL x,LL dep) {
	LL res=1;
	for (;dep;dep>>=1) {
		(dep&1)?(res=res*x%MOD):0;
		x=x*x%MOD;
	}
	return res;
}

int main(void) {
	// freopen("communicate.in","r",stdin);
	// freopen("communicate.out","w",stdout);
	freopen("data.in","r",stdin);
	n=read();
	rep(i,2,n) add_edge(read(),read());
	solve(1,0);
	ans=(ans*ksm(1LL*n*(n+1)%MOD*ny2%MOD,MOD-2)%MOD);
	printf("%lld\n", ans);
	return 0;
}