网站建设去哪里学,淄博网站设,网页开发需要学什么技术,WordPress游览器标签正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId2626 题目大意
给出nnn个点的一棵树#xff0c;每个区间[l,r][l,r][l,r]的代价是选出这个区间中的一个点xxx使得它走到所有点然后又回到xxx的路程最短长度#xff0c;求一个随机区间的期望代价。 1≤n…正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId2626 题目大意
给出nnn个点的一棵树每个区间[l,r][l,r][l,r]的代价是选出这个区间中的一个点xxx使得它走到所有点然后又回到xxx的路程最短长度求一个随机区间的期望代价。
1≤n≤1051\leq n\leq 10^51≤n≤105 解题思路
考虑统计每条边的贡献一条边会被记入当且仅当分成的两个树各存在一个点在区间中。
考虑怎么统计这个贡献计在两棵树中的点分别为000和111那么合法区间就是包含至少一个111和一个000的区间用线段树统计只包含000或111的区间减去即可。
然后在树上的问题所以直接上dsu on tree就好了。
时间复杂度O(nlog2n)O(n\log^2n)O(nlog2n)
然后写完题解突然发现线段树合并好像也行而且更快 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510,P1e97;
struct node{ll to,next;
}a[N1];
ll n,tot,ans,ls[N],siz[N],son[N];
ll w[N2],l0[N2],r0[N2],l1[N2],r1[N2];
void Merge(ll x,ll L,ll R){ll mid(LR)1;w[x]w[x*2]w[x*21]r0[x*2]*l0[x*21]r1[x*2]*l1[x*21];l0[x](l0[x*2]mid-L1)*l0[x*21]l0[x*2];r0[x](r0[x*21]R-mid)*r0[x*2]r0[x*21];l1[x](l1[x*2]mid-L1)*l1[x*21]l1[x*2];r1[x](r1[x*21]R-mid)*r1[x*2]r1[x*21];return;
}
void Build(ll x,ll L,ll R){if(LR){w[x]r0[x]l0[x]1;return;}ll mid(LR)1;Build(x*2,L,mid);Build(x*21,mid1,R);Merge(x,L,R);return;
}
void Change(ll x,ll L,ll R,ll pos){if(LR){swap(l0[x],l1[x]);swap(r0[x],r1[x]);return;}ll mid(LR)1;if(posmid)Change(x*2,L,mid,pos);else Change(x*21,mid1,R,pos);Merge(x,L,R);return;
}
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(ll x,ll fa){siz[x]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dfs(y,x);siz[x]siz[y];if(siz[y]siz[son[x]])son[x]y;}return;
}
void calc(ll x,ll fa){Change(1,1,n,x);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;calc(y,x);}return;
}
void solve(ll x,ll fa,ll top){for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa||yson[x])continue;solve(y,x,y);}if(son[x])solve(son[x],x,top);Change(1,1,n,x);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa||yson[x])continue;calc(y,x);}(ans(n*(n1)/2-w[1])%P)%P;if(xtop)calc(x,fa);return;
}
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
signed main()
{scanf(%lld,n);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}Build(1,1,n);dfs(1,1);solve(1,1,0);printf(%lld\n,ans*2*power(n*(n1)/2%P,P-2)%P);return 0;
}
