上海做淘宝网站,万网ip查询,装饰设计网站,怎样做水族馆网站正题
题目链接:https://www.luogu.com.cn/problem/P5666 题目大意
给出nnn个点的一棵树#xff0c;对于每条边割掉后两棵树重心编号和。 1≤T≤5,1≤n≤2999951\leq T\leq 5,1\leq n\leq 2999951≤T≤5,1≤n≤299995 解题思路
编号和#xff0c;所以应该是要我们枚举点然后…正题
题目链接:https://www.luogu.com.cn/problem/P5666 题目大意
给出nnn个点的一棵树对于每条边割掉后两棵树重心编号和。
1≤T≤5,1≤n≤2999951\leq T\leq 5,1\leq n\leq 2999951≤T≤5,1≤n≤299995 解题思路
编号和所以应该是要我们枚举点然后求有多少条边割掉后它能当重心。
随便以一个点为根的话对于一个点割掉它子树外面的一条边设割去的连通块大小为kkk那么需要满足以及点xxx的最大子节点子树为fxf_xfx {2(n−k−sx)≤n−S2fx≤n−k\left\{\begin{matrix}2(n-k-s_x)\leq n-S\\2f_x\leq n-k\end{matrix}\right.{2(n−k−sx)≤n−S2fx≤n−k 移一下项就有 n−2sx≤k≤n−2fxn-2s_x\leq k\leq n-2f_xn−2sx≤k≤n−2fx
但是子树里面就很难搞了因为我们需要维护子树里所有子树的大小其中一种方法是用线段树合并或者主席树像YbtOJ#662-交通运输这题一样搞。
很麻烦对啊吧转换一下思路。其实有一个性质就是如果我们选择了原树的重心作为根节点那么子节点无论如何割掉子树中的边也不会是重心。
所以这样就可以去掉这种麻烦的情况了。
只考虑前面那种我们需要找到分割大小在[n−2sx,n−2fx][n-2s_x,n-2f_x][n−2sx,n−2fx]这个区间的边并且还要不在子树内。
如果不考虑不在子树内的话挺好搞对于根节点到该节点的路径都是n−sizxn-siz_xn−sizx否则是sizxsiz_xsizx丢进树状数组里查询就好了边往下做边改树状数组就好了。
还要减去子树内的好像还是要和上面一样用线段树合并
我们可以用进入子树后的总共答案减去进入子树前的总共答案就是子树里面的答案了
这样好写很多时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
#define lowbit(x) (x-x)
using namespace std;
const ll N3e510;
struct node{ll to,next;
}a[N1];
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].toy;a[tot].nextls[x];ls[x]tot;return;
}
void Change(ll *t,ll x,ll val){x;while(xn1){t[x]val;xlowbit(x);}return;
}
ll Ask(ll *t,ll x){ll ans0;x;if(xn1)xn1;else if(x0)x0;while(x){anst[x];x-lowbit(x);}return ans;
}
void dfs(ll x,ll fa){siz[x]1;f[x]0;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dfs(y,x);siz[x]siz[y];f[x]max(f[x],siz[y]);}if(max(f[x],n-siz[x])n/2)rtx;return;
}
void calc(ll x,ll fa,bool flag){Change(t1,siz[fa],-1);Change(t1,n-siz[x],1);ll tmpAsk(t1,n-2*f[x])-Ask(t1,n-2*siz[x]-1);tmpAsk(t2,n-2*f[x])-Ask(t2,n-2*siz[x]-1);anstmp*x;ansrt*(siz[x]n-2*siz[flag?v:u]);Change(t2,siz[x],1);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)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));totrtansuv0;scanf(%lld,n);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}dfs(1,0);dfs(rt,0);for(ll ils[rt];i;ia[i].next){ll ya[i].to;if(siz[y]siz[u])vu,uy;else if(siz[y]siz[v])vy;} memset(t1,0,sizeof(t1));memset(t2,0,sizeof(t2));for(ll i1;in;i)Change(t1,siz[i],1);for(ll ils[rt];i;ia[i].next)calc(a[i].to,rt,(a[i].tou));printf(%lld\n,ans);} return 0;
}
