【题目链接】
http://www.lydsy.com/JudgeOnline/problem.php?id=3091
【思路】
膜Popoqqq大爷的题解 click here
【代码】是坑。。。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define FOR(a,b,c) for(int a=b;a<=c;a++) 5 #define trav(u,i) for(int i=front[u];i;i=e[i].nxt) 6 using namespace std; 7 8 typedef long long ll; 9 const int N = 4e5+10; 10 11 ll read() { 12 char c=getchar(); 13 ll f=1,x=0; 14 while(!isdigit(c)) { 15 if(c=='-') f=-1; c=getchar(); 16 } 17 while(isdigit(c)) 18 x=x*10+c-'0',c=getchar(); 19 return x*f; 20 } 21 22 namespace LCT { 23 24 struct Node { 25 Node *ch[2],*fa; 26 ll v,add,rev,ans,sum,ls,rs,siz; 27 Node() ; 28 void addv(ll x) { 29 add+=x; 30 v+=x; 31 sum+=siz*x; 32 ls+=x*siz*(siz+1)/2; 33 rs+=x*siz*(siz+1)/2; 34 ans+=x*siz*(siz+1)*(siz+2)/6; 35 } 36 void reverse() { 37 rev^=1; 38 swap(ls,rs); 39 swap(ch[0],ch[1]); 40 } 41 void up_push() { 42 if(fa->ch[0]==this||fa->ch[1]==this) 43 fa->up_push(); 44 if(rev) { 45 ch[0]->reverse(); 46 ch[1]->reverse(); 47 rev=0; 48 } 49 if(add) { 50 ch[0]->addv(add); 51 ch[1]->addv(add); 52 add=0; 53 } 54 } 55 void maintain() { 56 siz=ch[0]->siz+ch[1]->siz+1; 57 sum=ch[0]->sum+ch[1]->sum+v; 58 ls=ch[0]->ls+v*(ch[0]->siz+1)+ch[1]->ls+ch[1]->sum*(ch[0]->siz+1); 59 rs=ch[1]->rs+v*(ch[1]->siz+1)+ch[0]->rs+ch[0]->sum*(ch[1]->siz+1); 60 ans=ch[0]->ans+ch[1]->ans+(ch[1]->siz+1)*ch[0]->ls+(ch[0]->siz+1)*ch[1]->rs 61 +(ch[0]->siz+1)*(ch[1]->siz+1)*v; 62 } 63 } *null=new Node, T[N]; 64 Node::Node() { 65 ch[0]=ch[1]=fa=null; 66 v=rev=add=ans=sum=ls=rs=0; 67 siz=1; 68 } 69 void rot(Node* o,int d) { 70 Node* p=o->fa; 71 p->ch[d]=o->ch[d^1]; 72 o->ch[d^1]->fa=p; 73 o->ch[d^1]=p; 74 o->fa=p->fa; 75 if(p==p->fa->ch[0]) 76 p->fa->ch[0]=o; 77 else if(p==p->fa->ch[1]) 78 p->fa->ch[1]=o; 79 p->fa=o; 80 p->maintain(); 81 } 82 void splay(Node* o) { 83 o->up_push(); 84 Node *nf,*nff; 85 while(o->fa->ch[0]==o||o->fa->ch[1]==o) { 86 nf=o->fa,nff=nf->fa; 87 if(o==nf->ch[0]) { 88 if(nf==nff->ch[0]) rot(nf,0); 89 rot(o,0); 90 } else { 91 if(nf==nff->ch[1]) rot(nf,1); 92 rot(o,1); 93 } 94 } 95 o->maintain(); 96 } 97 void Access(Node* o) { 98 Node* son=null; 99 while(o!=null) { 100 splay(o); 101 o->ch[1]=son; 102 o->maintain(); 103 son=o; o=o->fa; 104 } 105 } 106 void evert(Node* o) { 107 Access(o); 108 splay(o); 109 o->reverse(); 110 } 111 void Link(Node* u,Node* v) { 112 evert(u); 113 u->fa=v; 114 } 115 void Cut(Node* u,Node* v) { 116 evert(u); 117 Access(v),splay(v); 118 v->ch[0]=u->fa=null; 119 v->maintain(); 120 } 121 Node* find(Node* o) { 122 while(o->fa!=null) o=o->fa; 123 return o; 124 } 125 126 } 127 using namespace LCT; 128 129 struct Edge { int v,nxt; 130 }e[N<<2]; 131 int en=1,front[N]; 132 void adde(int u,int v) 133 { 134 e[++en]=(Edge){v,front[u]}; front[u]=en; 135 } 136 137 int n,m; 138 139 void build(int u,int fa) 140 { 141 trav(u,i) { 142 int v=e[i].v; 143 if(v!=fa) { 144 T[v].fa=&T[u]; 145 build(v,u); 146 } 147 } 148 } 149 ll gcd(ll a,ll b) 150 { 151 return b? gcd(b,a%b):a; 152 } 153 154 int main() 155 { 156 freopen("in.in","r",stdin); 157 freopen("out.out","w",stdout); 158 null->siz=0; 159 scanf("%d%d",&n,&m); 160 FOR(i,1,n) { 161 ll x; 162 scanf("%lld",&x); 163 T[i].v=T[i].sum=T[i].ls=T[i].rs=T[i].ans=x; 164 } 165 int op,u,v; ll d; 166 FOR(i,1,n-1) { 167 scanf("%d%d",&u,&v); 168 adde(u,v),adde(v,u); 169 } 170 build(1,-1); 171 FOR(i,1,m) { 172 scanf("%d%d%%d",&op,&u,&v); 173 if(op==1) { 174 if(find(&T[u])==find(&T[v])) 175 Cut(&T[u],&T[v]); 176 } else 177 if(op==2) { 178 if(find(&T[u])!=find(&T[v])) 179 Link(&T[u],&T[v]); 180 } else 181 if(op==3) { 182 if(find(&T[u])==find(&T[v])) { 183 scanf("%lld",&d); 184 evert(&T[u]); 185 Access(&T[v]),splay(&T[v]); 186 T[v].addv(d); 187 } 188 } else { 189 if(find(&T[u])!=find(&T[v])) puts("-1"); 190 else { 191 evert(&T[u]); 192 Access(&T[v]),splay(&T[v]); 193 ll x=T[v].ans,y=T[v].siz*(T[v].siz+1)>>1; 194 ll g=gcd(x,y); 195 printf("%lld/%lld ",x/g,y/g); 196 } 197 } 198 } 199 return 0; 200 }