Description
Input
Output
- Sample Input
- 4 5
- 1 3 2 5
- 1 2
- 1 3
- 2 4
- 4 2 4
- 1 2 4
- 2 3 4
- 3 1 4 1
- 4 1 4
- Sample Output
- 16/3
- 6/1
- HINT
对于所有数据满足 1<=N<=50,000 1<=M<=50,000 1<=Ai<=10^6 1<=D<=100 1<=U,V<=N
题解 Here!
怎么 $LCT$ 还套了一个数学期望啊...
orz PoPoQQQ
$LCT$ 的大框架没争论.
然后看没有修改怎么办.
也就是那个期望值怎么求.
设每个点的权值为 $val_i$.
对于一条路径:$1-2-3-\cdots-n$
子路径数为 $C^2_{n+1}$.
也就是任选两个点, 包括两个点重复.
然后对于每个点 $i$, 一定会被 $i\times(n-i+1)$ 条路径覆盖.
即: 从左边选择端点或从右边选择端点或选 $i$ 为端点.
所以它的贡献就是 $val_i\times i\times(n-i+1)$.
于是期望值就可以这么算:$$exp=\frac{\sum_{i=1}^n(val_i\times i\times (n-i+1))}{C^2_{n+1}}$$
但是这玩意怎么维护呢?
那个分子直接维护 $size$ 即可, 所以丢一边去不管它.
再画图:
对于一条树上路径:$1-2-3-\cdots-x-(x+1)-(x+2)-\cdots-n$
假设 $x$ 为根节点.
那么左子树为:$1-2-3-\cdots-(x-1)$
其期望值为:$$exp_{lson}=\sum_{i=1}^{x-1}(val_i\times i\times (x-i))$$
但是实际要求的贡献为:$$exp_{lson}'=\sum_{i=1}^{x-1}(val_i\times i\times (n-i+1))$$
这个怎么办呢?
我们作个差试试:$$\left.\begin{array}{}exp_{lson}'-exp_{lson}&=&\sum_{i=1}^{x-1}(val_i\times i\times ((n-i+1)-(x-i)))\\&=&(n-x+1)\sum_{i=1}^{x-1}(val_i\times i)\end{array}\right.$$
额... 好像没什么用啊...
等一下!
那个 $(n-x+1)$ 很可疑啊!
没错! 它就是右子树的 $size+1$!(那个 $1$ 是根节点)
设:$$lsum_n=\sum_{i=1}^n(val_i\times i)$$
所以:$$exp_{lson}'=exp_{lson}+lsum_{lson}\times(size_{rson}+1)$$
同理对于右子树:
- $$rsum_n=\sum_{
- i=1
- }^n(val_i\times (n-i+1))$$
- $$exp_{
- rson
- }'=exp_{
- rson
- }+rsum_{
- rson
- }\times(size_{
- lson
- }+1)$$
然后是根节点的贡献:$$exp_{rt}'=val_{rt}\times(size_{lson}+1)\times(size_{rson}+1)$$
整到一块去:$$\left.\begin{array}{}exp_{rt}&=&exp_{rt}'+exp_{lson}'+exp_{rson}'\\&=&exp_{lson}+lsum_{lson}\times(size_{rson}+1)+exp_{rson}+rsum_{rson}\times(size_{lson}+1)+val_{rt}\times(size_{lson}+1)\times(size_{rson}+1)\end{array}\right.$$
那,$lsum_{rt},rsum_{rt}$ 怎么维护呢?
也很简单:
设 $$sum_{rt}=\sum_{i\in son_{rt}}val_i$$
则:$$lsum_{rt}=lsum_{lson}+lsum_{rson}+(val_{rt}+sum_{rson})\times(size_{lson}+1)$$
$$rsum_{rt}=rsum_{lson}+rsum_{rson}+(sum_{lson}+val_{rt})\times(size_{rson}+1)$$
终于把数学期望搞定了...
等一下!
好像还有修改?!
蒟蒻心里苦...
继续慢慢推式子...
假设在 $rt$ 加上的值为 $c$.
很显然:$$val_{rt}+=c$$
$$sum_{rt}+=c\times size_{rt}$$
那个 $lsum_{rt},rsum_{rt}$ 推一推式子也能出来:
- $$lsum_{
- rt
- }'=\sum_{i\in son_{rt}}((val_i+c)\times i)=\sum_{i\in son_{rt}}(val_i\times i)+c\times \frac{size_{rt}(size_{rt}+1)}{2}=lsum_{rt}+c\times \frac{size_{rt}(size_{rt}+1)}{2}$$
- $$rsum_{rt}'=rsum_{
- rt
- }+c\times \frac{
- size_{
- rt
- }(size_{
- rt
- }+1)
- }{
- 2
- }$$
但是 $exp_{rt}$ 就很恶心了...
与 $lsum_{rt}$ 的方法相同, 我们可以得到:$$exp_{rt}'=exp_{rt}+c\times \sum_{i=1}^{size_{rt}}(i\times(size_{rt}-i+1))$$
后面那一堆看得很烦, 于是挑出来搞事:$$S=\sum_{i=1}^{n}(i\times(n-i+1))=1\times n+2\times (n-1)+\cdots+n\times 1$$
补项成我们会的东东:$$S=(1+2+3+\cdots+n)\times n-(1\times 2+2\times 3+\cdots+(n-1)\times n)$$
前面一部分好说, 继续把后面一部分挑出来搞事:
- $$S=\frac{
- n^2(n+1)
- }{
- 2
- }-W$$
- $$W=(1\times 2+2\times 3+\cdots+(n-1)\times n)$$
拆项成我们会的东东:
$$\left.\begin{array}{}W&=&1\times 2+2\times 3+\cdots+(n-1)\times n\\&=&1^2+2^2+3^2+\cdots+(n-1)^2+1+2+3+\cdots+(n-1)\end{array}\right.$$
根据小学奥数 / 高中必修, 我们可以得到:$$W=\frac{n(n-1)(2n-1)}{6}+\frac{n(n-1)}{2}$$
于是:$$S=\frac{n^2(n+1)}{2}-\frac{n(n-1)(2n-1)}{6}-\frac{n(n-1)}{2}$$
然后疯狂展开, 疯狂合并同类项, 最后得到一个简单到难以想象的式子:$$S=\frac{n(n+1)(n+2)}{6}$$
整个还回去:$$exp_{rt}'=exp_{rt}+c\times\frac{size_{rt}(size_{rt}+1)(size_{rt}+2)}{6}$$
修改也就完成了.
记得翻转的时候把 $lsum_{rt},rsum_{rt}$ 也交换一下.
然后用一个 $map$ 大力记录边.
记得开 $long\ long$.
呼~~~
终于写完了...
累死我了...
鬼畜的神题...
其实我写的还不是很好, 但是我已经尽力了...
看不懂的, 就去找代码吧...
附代码:
- #include<iostream>
- #include<algorithm>
- #include<cstdio>
- #include<map>
- #define MAXN 50010
- using namespace std;
- map<int,int> Edge[MAXN];
- int n,m;
- int top=0,stack[MAXN];
- struct Link_Cut_Tree{
- int f,size,flag,son[2];
- long long val,sum,lsum,rsum,exp,c;//exp==expectation
- }a[MAXN];
- inline int read(){
- int date=0,w=1;char c=0;
- while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
- while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
- return date*w;
- }
- long long gcd(long long x,long long y){
- if(!y)return x;
- return gcd(y,x%y);
- }
- inline bool isroot(int rt){
- return a[a[rt].f].son[0]!=rt&&a[a[rt].f].son[1]!=rt;
- }
- inline void pushup(int rt){
- if(!rt)return;
- int lson=a[rt].son[0],rson=a[rt].son[1];
- a[rt].sum=a[lson].sum+a[rson].sum+a[rt].val;
- a[rt].size=a[lson].size+a[rson].size+1;
- a[rt].lsum=a[lson].lsum+a[rson].lsum+(a[rt].val+a[rson].sum)*(a[lson].size+1);
- a[rt].rsum=a[rson].rsum+a[lson].rsum+(a[lson].sum+a[rt].val)*(a[rson].size+1);
- a[rt].exp=a[lson].exp+a[rson].exp+a[rt].val*(a[lson].size+1)*(a[rson].size+1)+a[lson].lsum*(a[rson].size+1)+a[rson].rsum*(a[lson].size+1);
- }
- inline void reverse(int rt){
- if(!rt)return;
- a[rt].flag^=1;
- swap(a[rt].son[0],a[rt].son[1]);
- swap(a[rt].lsum,a[rt].rsum);
- }
- inline void change(int rt,long long c){
- if(!rt)return;
- long long x=1LL*a[rt].size*(a[rt].size+1)/2,y=1LL*a[rt].size*(a[rt].size+1)*(a[rt].size+2)/6;
- a[rt].val+=c;
- a[rt].c+=c;
- a[rt].sum+=c*a[rt].size;
- a[rt].lsum+=x*c;
- a[rt].rsum+=x*c;
- a[rt].exp+=c*y;
- }
- inline void pushdown(int rt){
- if(!rt)return;
- if(a[rt].flag){
- reverse(a[rt].son[0]);
- reverse(a[rt].son[1]);
- a[rt].flag=0;
- }
- if(a[rt].c){
- change(a[rt].son[0],a[rt].c);
- change(a[rt].son[1],a[rt].c);
- a[rt].c=0;
- }
- }
- inline void turn(int rt){
- int x=a[rt].f,y=a[x].f,k=a[x].son[0]==rt?1:0;
- if(!isroot(x)){
- if(a[y].son[0]==x)a[y].son[0]=rt;
- else a[y].son[1]=rt;
- }
- a[rt].f=y;a[x].f=rt;a[a[rt].son[k]].f=x;
- a[x].son[k^1]=a[rt].son[k];a[rt].son[k]=x;
- pushup(x);pushup(rt);
- }
- void splay(int rt){
- top=0;
- stack[++top]=rt;
- for(int i=rt;!isroot(i);i=a[i].f)stack[++top]=a[i].f;
- while(top)pushdown(stack[top--]);
- while(!isroot(rt)){
- int x=a[rt].f,y=a[x].f;
- if(!isroot(x)){
- if((a[y].son[0]==x)^(a[x].son[0]==rt))turn(rt);
- else turn(x);
- }
- turn(rt);
- }
- }
- void access(int rt){
- for(int i=0;rt;i=rt,rt=a[rt].f){
- splay(rt);
- a[rt].son[1]=i;
- pushup(rt);
- }
- }
- inline void makeroot(int rt){access(rt);splay(rt);reverse(rt);}
- int findroot(int rt){
- access(rt);splay(rt);
- while(a[rt].son[0])rt=a[rt].son[0];
- return rt;
- }
- inline void split(int x,int y){makeroot(x);access(y);splay(y);}
- inline void link(int x,int y){makeroot(x);a[x].f=y;}
- inline void cut(int x,int y){
- split(x,y);
- if(a[y].son[0]==x&&a[x].f==y&&!a[x].son[1])a[x].f=a[y].son[0]=0;
- pushup(y);
- }
- inline void update(int x,int y,int k){
- split(x,y);
- change(y,k);
- }
- inline void query(int x,int y){
- long long on,down,t;
- split(x,y);
- on=a[y].exp;
- down=1LL*a[y].size*(a[y].size+1)/2;
- t=gcd(on,down);
- printf("%lld/%lld\n",on/t,down/t);
- }
- void work(){
- int f,x,y,k;
- while(m--){
- f=read();x=read();y=read();
- switch(f){
- case 1:{
- if(Edge[x][y]){
- cut(x,y);
- Edge[x][y]=Edge[y][x]=0;
- }
- break;
- }
- case 2:{
- if(findroot(x)!=findroot(y)){
- link(x,y);
- Edge[x][y]=Edge[y][x]=1;
- }
- break;
- }
- case 3:{
- k=read();
- if(findroot(x)!=findroot(y))break;
- update(x,y,k);
- break;
- }
- case 4:{
- if(findroot(x)!=findroot(y))printf("-1\n");
- else query(x,y);
- break;
- }
- }
- }
- }
- void init(){
- int x,y;
- n=read();m=read();
- for(int i=1;i<=n;i++){
- a[i].val=read();
- pushup(i);
- }
- for(int i=1;i<n;i++){
- x=read();y=read();
- Edge[x][y]=Edge[y][x]=1;
- link(x,y);
- }
- }
- int main(){
- init();
- work();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2975078.html