題目鏈接

http://codeforces.com/contest/482/problem/E

題解

T2智商題T3大LCT題，我一個也不會= =
CF的標算好像是分塊？反正現在LCT都普及了就用LCT好了。

首先算期望推個式子，易得答案為\(\sum_u a[u](sz[u]^2-\sum_{v\in son[u]} sz[v]^2)\) (\(sz\)為子樹大小)，令求和的那個東西等于\(f[u]\)
并且如果往一個\(u\)里新添一個兒子\(v\)，增添后的子樹大小是\(sz[v]\), 那么新增的答案是\(a[u]sz[v](sz[u]-sz[v])\)
然后我們要支持換父親，動態維護這個東西

后面的就是莽上一個LCT。
這個只能詳見代碼，解釋一下代碼里變量的含義
對于一個Splay結構體\(u\):
\(ans\): 這個點Splay的子樹中所有點的\(f\)之和。Splay的根的\(ans\)就是要求的答案。
\(sz01\): 這個點所有虛子樹的大小之和加上本身的\(1\)。(\(sz\)是原樹中子樹大小)
\(sz02\): 這個點本身所有虛子樹的大小平方和，不包括本身。
\(ans0\): 這個點本身所有虛兒子的\(ans\)之和。
\(sz11\): 這個點所有實兒子和虛兒子的大小之和。
\(sum\): 這個點所有實兒子\(v\)的\(sz01[v]\times a[v]\)之和。
這些變量看起來有些匪夷所思，那么我們看下怎么維護。
首先，所有對虛兒子求和的變量(也就是名字里帶0的三個)都在access時處理，pushup時無需處理。
現在考慮pushup那個函數，前兩行處理的是\(sz11\)和\(sum\), 這個根據定義求就行，也沒有什么好說的。
后四行是重點——\(ans\)的更新。

我們把\(ans[u]\)分了四部分統計。(選兩個點\(x\)和\(y\)求\(a[lca(x,y)]\)之和)
第一部分: 兩個點都選在\(u\)的祖先(splay左子樹內)，或都選在splay右子樹內，或都選在\(u\)的同一棵虛子樹內。

spl[u].ans = spl[ls].ans+spl[u].ans0+spl[rs].ans;

第二部分: 兩個點選在\(u\)的兩棵不同虛子樹內。

spl[u].ans += (spl[u].sz01*spl[u].sz01-spl[u].sz02)*a[u];

第三部分: 兩個點之一選在\(u\)的虛子樹內，另一個點選在\(u\)的splay右子樹內。這樣LCA一定是\(u\).

spl[u].ans += 2ll*spl[u].sz01*spl[rs].sz11*a[u];

第四部分: 兩個點之一選在\(u\)的祖先(splay左子樹)或其虛子樹內，另一個選在\(u\)的整個splay子樹及子樹內所有點的虛子樹去掉\(u\)上方(splay左子樹內及其虛子樹)的部分，也就是\(u\)及其下方(splay右子樹內)所有點及其虛子樹內。

spl[u].ans += 2ll*spl[ls].sum*(spl[u].sz11-spl[ls].sz11);

于是就做完了。(第四部分確實有點復雜)

最后膜拜一發考場切此題的新初三巨佬
zjr nb!

代碼

#include<cstdio> #include<cstdlib> #include<iostream> #define llong long long using namespace std;void read(int &x) {int f=1;x=0;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}x*=f; }const int N = 1e5; struct SplayNode {int son[2],fa; llong sz01,sz11,sz02,sum,ans0,ans; } spl[N+3]; int fa[N+3]; llong a[N+3]; int n,q;bool isroot(int u) {return spl[spl[u].fa].son[0]!=u && spl[spl[u].fa].son[1]!=u;}void pushup(int u) {int ls = spl[u].son[0],rs = spl[u].son[1];spl[u].sz11 = spl[ls].sz11+spl[u].sz01+spl[rs].sz11;spl[u].sum = spl[ls].sum+spl[rs].sum+spl[u].sz01*a[u];spl[u].ans = spl[ls].ans+spl[u].ans0+spl[rs].ans;spl[u].ans += (spl[u].sz01*spl[u].sz01-spl[u].sz02)*a[u];spl[u].ans += 2ll*spl[u].sz01*spl[rs].sz11*a[u];spl[u].ans += 2ll*spl[ls].sum*(spl[u].sz11-spl[ls].sz11); }void rotate(int u) {int x = spl[u].fa,y = spl[x].fa;spl[u].fa = y;if(!isroot(x)) {spl[y].son[x==spl[y].son[1]] = u;}int dir = u==spl[x].son[0];spl[x].son[dir^1] = spl[u].son[dir];if(spl[u].son[dir]) {spl[spl[u].son[dir]].fa = x;}spl[u].son[dir] = x; spl[x].fa = u;pushup(x); pushup(u); }void splaynode(int u) {while(!isroot(u)){int x = spl[u].fa,y = spl[x].fa;if(!isroot(x)) {x==spl[y].son[1] ^ u==spl[x].son[1] ? rotate(u) : rotate(x);}rotate(u);}pushup(u); }void access(int u) {for(int i=0; u; i=u,u=spl[u].fa){splaynode(u);int ls = spl[u].son[0],rs = spl[u].son[1];spl[u].sz01 += spl[rs].sz11;spl[u].sz02 += spl[rs].sz11*spl[rs].sz11;spl[u].ans0 += spl[rs].ans; //not ans0rs = spl[u].son[1] = i;spl[u].sz01 -= spl[rs].sz11;spl[u].sz02 -= spl[rs].sz11*spl[rs].sz11;spl[u].ans0 -= spl[rs].ans;pushup(u);} }void link(int u,int v) {access(v); splaynode(v);access(u); splaynode(u); //in order to pushupspl[u].sz01 += spl[v].sz11;spl[u].sz02 += spl[v].sz11*spl[v].sz11;spl[u].ans0 += spl[v].ans;spl[v].fa = u;pushup(u); }void cut(int u,int v) {access(u); splaynode(u);splaynode(v); //v is in the virtual subtree of uspl[u].sz01 -= spl[v].sz11;spl[u].sz02 -= spl[v].sz11*spl[v].sz11;spl[u].ans0 -= spl[v].ans;spl[v].fa = 0;pushup(u); }bool isanc(int u,int v) //if u is ancestor of v {access(v); splaynode(v);splaynode(u);if(!isroot(v)) return true;return false; }void printans(llong x) {double ans = (double)x/(double)n/(double)n;printf("%.12lf\n",ans); }int main() {scanf("%d",&n);for(int i=2; i<=n; i++) scanf("%d",&fa[i]);for(int i=1; i<=n; i++) scanf("%I64d",&a[i]);for(int i=1; i<=n; i++) spl[i].sz11 = spl[i].sz01 = 1ll,spl[i].ans = spl[i].sum = a[i];for(int i=2; i<=n; i++){link(fa[i],i);}access(1); splaynode(1);printans(spl[1].ans);scanf("%d",&q);for(int i=1; i<=q; i++){char opt[5]; scanf("%s",opt+1);if(opt[1]=='P'){int x,y; scanf("%d%d",&x,&y);if(isanc(x,y)) {swap(x,y);}cut(fa[x],x);fa[x] = y;link(fa[x],x);access(1); splaynode(1);printans(spl[1].ans);}else if(opt[1]=='V'){int x; llong y; scanf("%d%I64d",&x,&y);access(x); splaynode(x);a[x] = y;pushup(x);printans(spl[x].ans);}}return 0; }

總結

以上是生活随笔為你收集整理的Codeforces 482E ELCA (LCT)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。