正題

---

題目大意

$n$個(gè)節(jié)點(diǎn)的一棵樹，隨機(jī)選擇一個(gè)區(qū)間，求這個(gè)區(qū)間的點(diǎn)所構(gòu)成的虛樹的期望權(quán)值和。

---

解題思路

考慮每一條邊的貢獻(xiàn)，定義一邊的點(diǎn)為黑點(diǎn)，一邊的為白點(diǎn)，顯然包含黑白的區(qū)間都會(huì)產(chǎn)生貢獻(xiàn)。考慮減去沒有貢獻(xiàn)的，也就是對(duì)于連續(xù)的一段長度為$l$的顏色相同的區(qū)間會(huì)產(chǎn)生貢獻(xiàn)$\frac{n(n+1)}{2}$

用線段樹維護(hù)然后合并即可。

時(shí)間復(fù)雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10,M=N*20,XJQ=1e9+7; ll f(ll n) {return n*(n-1)/2;} struct Seg_Tree{ll cnt,ls[M],rs[M],lb[M],rb[M],lw[M],rw[M],ans[M];void PushUp(ll x,ll L,ll R){ll mid=(L+R)>>1;if(!ls[x])ls[x]=++cnt,lb[cnt]=rb[cnt]=(mid-L+1),ans[cnt]=f(mid-L+1);if(!rs[x])rs[x]=++cnt,lb[cnt]=rb[cnt]=(R-mid),ans[cnt]=f(R-mid);ans[x]=ans[ls[x]]+ans[rs[x]];ans[x]=ans[x]-f(rb[ls[x]])-f(lb[rs[x]])+f(rb[ls[x]]+lb[rs[x]]);ans[x]=ans[x]-f(rw[ls[x]])-f(lw[rs[x]])+f(rw[ls[x]]+lw[rs[x]]);lb[x]=(lb[ls[x]]==mid-L+1)?(lb[ls[x]]+lb[rs[x]]):lb[ls[x]];rb[x]=(rb[rs[x]]==R-mid)?(rb[rs[x]]+rb[ls[x]]):rb[rs[x]];lw[x]=(lw[ls[x]]==mid-L+1)?(lw[ls[x]]+lw[rs[x]]):lw[ls[x]];rw[x]=(rw[rs[x]]==R-mid)?(rw[rs[x]]+rw[ls[x]]):rw[rs[x]];}void Change(ll &x,ll l,ll r,ll pos){if(!x)x=++cnt;if(l==r){lw[x]=rw[x]=1;return;}ll mid=(l+r)>>1;if(pos<=mid)Change(ls[x],l,mid,pos);else Change(rs[x],mid+1,r,pos);PushUp(x,l,r);}ll Merge(ll x,ll y,ll l,ll r){if(!x||!y)return x+y;if(lb[x]==r-l+1)return y;if(lb[y]==r-l+1)return x;ll mid=(l+r)>>1;ls[x]=Merge(ls[x],ls[y],l,mid);rs[x]=Merge(rs[x],rs[y],mid+1,r);PushUp(x,l,r);return x;} }T; struct node{ll to,next; }a[N*2]; ll n,tot,ls[N],rt[N],ans; void addl(ll x,ll y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } ll power(ll x,ll b){ll ans=1;x%=XJQ;while(b){if(b&1)ans=ans*x%XJQ;x=x*x%XJQ;b>>=1;}return ans; } void dfs(ll x,ll fa){T.Change(rt[x],1,n,x);for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa)continue;dfs(y,x);T.Merge(rt[x],rt[y],1,n);}ans+=f(n)-T.ans[rt[x]];return; } int main() {freopen("communicate.in","r",stdin);freopen("communicate.out","w",stdout);scanf("%lld",&n);for(ll i=1;i<n;i++){ll x,y;scanf("%lld%lld",&x,&y);addl(x,y);addl(y,x);}dfs(1,1);ans=ans*2%XJQ;printf("%lld",ans*power(n*(n+1)/2,XJQ-2)%XJQ); }

總結(jié)

以上是生活随笔為你收集整理的jzoj5365-[GDOI2018模拟9.14]通信【线段树合并】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。