正題

題目鏈接:https://www.luogu.com.cn/problem/P5666

---

題目大意

給出$n$個點的一棵樹，對于每條邊割掉后兩棵樹重心編號和。

$1\le T\le 5,1\le n\le 299995$

---

解題思路

編號和，所以應(yīng)該是要我們枚舉點然后求有多少條邊割掉后它能當重心。

隨便以一個點為根的話，對于一個點，割掉它子樹外面的一條邊，設(shè)割去的連通塊大小為$k$那么需要滿足，以及點$x$的最大子節(jié)點子樹為$f_x$
$$\{\begin{array}{c}2(n?k?s_x)\le n?S\\ 2f_x\le n?k\end{array}$$
移一下項就有
$$n?2s_x\le k\le n?2f_x$$

但是子樹里面就很難搞了，因為我們需要維護子樹里所有子樹的大小，其中一種方法是用線段樹合并或者主席樹像YbtOJ#662-交通運輸這題一樣搞。

很麻煩對啊吧，轉(zhuǎn)換一下思路。其實有一個性質(zhì)就是如果我們選擇了原樹的重心作為根節(jié)點，那么子節(jié)點無論如何割掉子樹中的邊也不會是重心。

所以這樣就可以去掉這種麻煩的情況了。

只考慮前面那種，我們需要找到分割大小在$[n?2s_x,n?2f_x]$這個區(qū)間的邊，并且還要不在子樹內(nèi)。

如果不考慮不在子樹內(nèi)的話挺好搞，對于根節(jié)點到該節(jié)點的路徑都是$n?si{z}_x$，否則是$si{z}_x$丟進樹狀數(shù)組里查詢就好了，邊往下做邊改樹狀數(shù)組就好了。

還要減去子樹內(nèi)的，好像還是要和上面一樣用線段樹合并？

我們可以用進入子樹后的總共答案減去進入子樹前的總共答案就是子樹里面的答案了

這樣好寫很多，時間復(fù)雜度$O(n\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define lowbit(x) (x&-x) using namespace std; const ll N=3e5+10; struct node{ll to,next; }a[N<<1]; ll T,n,ans,tot,rt,u,v; ll siz[N],f[N],ls[N],t1[N],t2[N]; void addl(ll x,ll y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void Change(ll *t,ll x,ll val){x++;while(x<=n+1){t[x]+=val;x+=lowbit(x);}return; } ll Ask(ll *t,ll x){ll ans=0;x++;if(x>=n+1)x=n+1;else if(x<0)x=0;while(x){ans+=t[x];x-=lowbit(x);}return ans; } void dfs(ll x,ll fa){siz[x]=1;f[x]=0;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa)continue;dfs(y,x);siz[x]+=siz[y];f[x]=max(f[x],siz[y]);}if(max(f[x],n-siz[x])<=n/2)rt=x;return; } void calc(ll x,ll fa,bool flag){Change(t1,siz[fa],-1);Change(t1,n-siz[x],1);ll tmp=Ask(t1,n-2*f[x])-Ask(t1,n-2*siz[x]-1);tmp+=Ask(t2,n-2*f[x])-Ask(t2,n-2*siz[x]-1);ans+=tmp*x;ans+=rt*(siz[x]<=n-2*siz[flag?v:u]);Change(t2,siz[x],1);for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa)continue;calc(y,x,flag);}Change(t1,siz[fa],1);Change(t1,n-siz[x],-1);ans-=(Ask(t2,n-2*f[x])-Ask(t2,n-2*siz[x]-1))*x; } signed main() {scanf("%lld",&T);while(T--){memset(ls,0,sizeof(ls));tot=rt=ans=u=v=0;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,0);dfs(rt,0);for(ll i=ls[rt];i;i=a[i].next){ll y=a[i].to;if(siz[y]>siz[u])v=u,u=y;else if(siz[y]>siz[v])v=y;} memset(t1,0,sizeof(t1));memset(t2,0,sizeof(t2));for(ll i=1;i<=n;i++)Change(t1,siz[i],1);for(ll i=ls[rt];i;i=a[i].next)calc(a[i].to,rt,(a[i].to==u));printf("%lld\n",ans);} return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的P5666-[CSP-S2019]树的重心【树状数组】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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