首页 > 代码库 > BZOJ 3091 城市旅行 Link-Cut-Tree
BZOJ 3091 城市旅行 Link-Cut-Tree
警告:此题不可以使用cout进行输出,只能用printf,否则RE!亲测!!
题目大意:给定一棵树,每个点有一个点权,提供四种操作:
1.删除两点之间的连边 不存在边则无视
2.在两点之前连接一条边 两点已经联通则无视
3.在两点之间的路径上所有点的点权加上一个数 两点不连通则无视
4.询问两点之间路径上任选两点路径上的点权和的期望值
前三个操作都很基础 但是第四个东西……这啥玩应这是……
首先这个期望值等于路径上所有无序点对路径上权值和的平均值 还是很抽象?没关系,拿样例说话
样例第一个询问 2到4 我们有三个点对(2,2)(2,4)(4,4) 路径上的权值和分别为3 8 5 于是平均值为16/3
如果两点之间的点数为n 那么分母很明显是C(n+1,2)=n*(n+1)/2 考虑维护分子
如图所示,第一个点对答案的贡献为a1*1*n(左端点只能选a1,右端点可以选a1~an),第二个点对答案的贡献为a2*2*(n-1)(左端点可以选a1或a2,右端点可以选a2~an)
于是答案就是a1*1*n+a2*2*(n-1)+...+an*n*1 这个东西显然不能暴力求 需要在LCT上维护 但是直接维护根本维护不了 怎么办呢?
如图,维护之前是上面的样子,我们要把它变成下面的样子,怎么办呢?
观察左子树 将左子树合并前后的贡献值作差可得
我们发现这个3其实就是右子树的size+1
于是我们令lsum=1*a1+2*a2+...+n*an,同理有rsum=1*an+2*an-1+...+n*a1
于是就有exp=ls->exp+rs->exp+ls->lsum*(rs->size+1)+rs->rsum*(ls->size+1)+num*(ls->size+1)*(rs->size+1)
其中最后一项是root本身对答案的贡献,num为root节点的权值
lsum和rsum维护比较简单,不说了。(如果有挂在这里的人千万别骂我!)
此外修改时lsum和rsum加的都是x*(1+2+...+n)=x*n*(n+1)/2,可是exp加的东西是x*(1*n+2*(n-1)+...+n*1),这个怎么算呢?
打表?不用。有公式的:1*n+2*(n-1)+...+n*1=n*(n+1)*(n+2)/6 万能的数学啊
最后就是不要写cout 从早上RE到现在……又尼玛是血的教训…… 坑比啊
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 50500 using namespace std; typedef unsigned long long ll; struct abcd{ abcd *ls,*rs,*fa; ll num,size; ll sum,lsum,rsum,exp; bool rev_mark; ll add_mark; abcd(int x); void Push_Up(); void Push_Down(); void Reverse(); void Add(ll x); }*null=new abcd(0),*tree[M]; abcd :: abcd(int x) { ls=rs=fa=null; num=x;size=null?1:0; sum=lsum=rsum=exp=x; rev_mark=false; add_mark=0; } void abcd :: Push_Up() { size = ls->size + rs->size + 1; sum = ls->sum + rs->sum + num; lsum = ls->lsum + num*(ls->size+1) + rs->lsum + rs->sum*(ls->size+1); rsum = rs->rsum + num*(rs->size+1) + ls->rsum + ls->sum*(rs->size+1); exp = ls->exp + rs->exp + (rs->size+1)*ls->lsum + (ls->size+1)*rs->rsum + (ls->size+1)*(rs->size+1)*num; } void abcd :: Push_Down() { if(fa->ls==this||fa->rs==this) fa->Push_Down(); if(rev_mark) { ls->Reverse(); rs->Reverse(); rev_mark=0; } if(add_mark) { ls->Add(add_mark); rs->Add(add_mark); add_mark=0; } } void abcd :: Reverse() { swap(lsum,rsum); swap(ls,rs); rev_mark^=1; } void abcd :: Add(ll x) { if(this==null) return ; num+=x; sum+=x*size; lsum+=x*size*(size+1)/2; rsum+=x*size*(size+1)/2; exp+=x*size*(size+1)*(size+2)/6; add_mark+=x; } void Zig(abcd *x) { abcd *y=x->fa; y->ls=x->rs; x->rs->fa=y; x->rs=y; x->fa=y->fa; if(y==y->fa->ls) y->fa->ls=x; else if(y==y->fa->rs) y->fa->rs=x; y->fa=x; y->Push_Up(); } void Zag(abcd *x) { abcd *y=x->fa; y->rs=x->ls; x->ls->fa=y; x->ls=y; x->fa=y->fa; if(y==y->fa->ls) y->fa->ls=x; else if(y==y->fa->rs) y->fa->rs=x; y->fa=x; y->Push_Up(); } void Splay(abcd *x) { x->Push_Down(); while(x->fa->ls==x||x->fa->rs==x) { abcd *y=x->fa,*z=y->fa; if(x==y->ls) { if(y==z->ls) Zig(y); Zig(x); } else { if(y==z->rs) Zag(y); Zag(x); } } x->Push_Up(); } void Access(abcd *x) { abcd *y=null; while(x!=null) { Splay(x); x->rs=y; x->Push_Up(); y=x; x=x->fa; } } void Move_To_Root(abcd *x) { Access(x); Splay(x); x->Reverse(); } abcd* Find_Root(abcd *x) { while(x->fa!=null) x=x->fa; return x; } void Link(abcd *x,abcd *y) { if(Find_Root(x)==Find_Root(y)) return ; Move_To_Root(x); x->fa=y; } void Cut(abcd *x,abcd *y) { if(x==y||Find_Root(x)!=Find_Root(y)) return ; Move_To_Root(x); Access(y); Splay(y); if(y->ls==x&&x->rs==null) { x->fa=null; y->ls=null; y->Push_Up(); } } struct edge{ int to,next; }table[M<<1]; int head[M],tot; int n,m; void Add(int x,int y) { table[++tot].to=y; table[tot].next=head[x]; head[x]=tot; } void DFS(int x,int from) { int i; if(from) tree[x]->fa=tree[from]; for(i=head[x];i;i=table[i].next) { if(table[i].to==from) continue; DFS(table[i].to,x); } } void Modify(abcd *x,abcd *y) { int z; scanf("%d",&z); if(Find_Root(x)!=Find_Root(y)) return ; Move_To_Root(x); Access(y); Splay(y); y->Add(z); } ll GCD(ll x,ll y) { return y?GCD(y,x%y):x; } void Query(abcd *x,abcd *y) { if(Find_Root(x)!=Find_Root(y)) { puts("-1"); return ; } Move_To_Root(x); Access(y); Splay(y); ll a=y->exp; ll b=y->size*(y->size+1)>>1; ll gcd=GCD(a,b); //cout<<(a/gcd)<<'/'<<(b/gcd)<<endl; //不能写cout 否则RE TM一上午就卡在这了 printf("%lld/%lld\n",a/gcd,b/gcd); } int main() { ///freopen("travel.in","r",stdin); ///freopen("travel.out","w",stdout); int i,p,x,y; cin>>n>>m; for(i=1;i<=n;i++) scanf("%d",&x),tree[i]=new abcd(x); for(i=1;i<n;i++) { scanf("%d%d",&x,&y); Add(x,y);Add(y,x); } DFS(1,0); for(i=1;i<=m;i++) { scanf("%d%d%d",&p,&x,&y); switch(p) { case 1:Cut(tree[x],tree[y]);break; case 2:Link(tree[x],tree[y]);break; case 3:Modify(tree[x],tree[y]);break; case 4:Query(tree[x],tree[y]);break; } } }
BZOJ 3091 城市旅行 Link-Cut-Tree