题目大意
给你一棵树, 每个点有一个点权.
有两种操作:
- link / cut
- 修改某个点的点权
每次操作后, 你要输出以下答案: 在整棵树中任意选两个点, 这两个点的LCA的期望权值.
Solution
我们考虑每个点作为LCA的概率:
\[P(u为LCA) = \frac{sz[u]^2 - \sum_{v为u的子节点} sz[v]^2}{n^2}
\]
\]
所以我们的答案为
\[\begin{aligned}
E &= \frac{\sum_{每个节点u} (sz[u]^2 - \sum_{v为u的字节点} sz[v]^2) a[u]}{n^2} \\ &= \frac{\sum_{每个节点u} (a[u] - a[fa[u]]) sz[u]^2}{n^2}
\end{aligned}
\]
E &= \frac{\sum_{每个节点u} (sz[u]^2 - \sum_{v为u的字节点} sz[v]^2) a[u]}{n^2} \\ &= \frac{\sum_{每个节点u} (a[u] - a[fa[u]]) sz[u]^2}{n^2}
\end{aligned}
\]
考虑每次操作的改变量, 把平方拆开维护即可.
link-cut tree真的非常不熟练啊!!!!!
#include <cstdio>
#include <cctype>
#include <set>
using namespace std;
namespace Zeonfai
{
inline int getInt()
{
int a = 0, sgn = 1; char c;
while(! isdigit(c = getchar())) if(c == '-') sgn *= -1;
while(isdigit(c)) a = a * 10 + c - '0', c = getchar();
return a * sgn;
}
}
const int N = (int)1e5;
int n;
double ans;
inline long long sqr(int a) {return (long long)a * a;}
struct linkCutTree
{
struct node
{
int suc[2], pre, isRoot;
int a;
int lst; set<int> bck;
int sz, tg;
long long differenceSum, productSum;
inline node()
{
for(int i = 0; i < 2; ++ i) suc[i] = -1; pre = -1; isRoot = 1;
a = 0;
lst = -1; bck.clear();
sz = 1; tg = 0; // 维护原树中的size
differenceSum = productSum = 0; // 重链上的和
}
}nd[N + 1];
inline void pushDown(int u)
{
if(! nd[u].isRoot) pushDown(nd[u].pre);
for(int i = 0; i < 2; ++ i) if(~ nd[u].suc[i])
{
nd[nd[u].suc[i]].tg += nd[u].tg; nd[nd[u].suc[i]].sz += nd[u].tg;
nd[nd[u].suc[i]].productSum += nd[u].tg * nd[nd[u].suc[i]].differenceSum;
}
nd[u].tg = 0;
}
inline int getRelation(int u) {return nd[u].isRoot ? - 1 : u == nd[nd[u].pre].suc[1];}
inline void update(int u)
{
nd[u].differenceSum = nd[u].a - (~ nd[u].lst ? nd[nd[u].lst].a : 0);
nd[u].productSum = nd[u].sz * nd[u].differenceSum;
for(int i = 0; i < 2; ++ i) if(~ nd[u].suc[i])
nd[u].differenceSum += nd[nd[u].suc[i]].differenceSum,
nd[u].productSum += nd[nd[u].suc[i]].productSum;
}
inline void rotate(int u)
{
int pre = nd[u].pre, prepre = nd[pre].pre, k = getRelation(u);
if(~ nd[u].suc[k ^ 1]) nd[nd[u].suc[k ^ 1]].pre = pre; nd[pre].suc[k] = nd[u].suc[k ^ 1];
nd[u].pre = prepre; if(! nd[pre].isRoot) nd[prepre].suc[getRelation(pre)] = u;
nd[pre].pre = u; nd[u].suc[k ^ 1] = pre;
if(nd[pre].isRoot) nd[pre].isRoot = 0, nd[u].isRoot = 1;
update(pre); update(u);
}
inline void splay(int u)
{
pushDown(u);
while(! nd[u].isRoot)
{
if(! nd[nd[u].pre].isRoot) rotate(getRelation(u) == getRelation(nd[u].pre) ? nd[u].pre : u);
rotate(u);
}
}
inline void access(int u)
{
splay(u);
if(~ nd[u].suc[1])
{
nd[u].productSum -= nd[nd[u].suc[1]].productSum;
nd[u].differenceSum -= nd[nd[u].suc[1]].differenceSum;
nd[nd[u].suc[1]].isRoot = 1; nd[u].suc[1] = -1;
}
while(~ nd[u].pre)
{
int pre = nd[u].pre; splay(pre);
if(~ nd[pre].suc[1])
{
nd[pre].productSum -= nd[nd[pre].suc[1]].productSum;
nd[pre].differenceSum -= nd[nd[pre].suc[1]].differenceSum;
nd[nd[pre].suc[1]].isRoot = 1; nd[pre].suc[1] = -1;
}
nd[pre].productSum += nd[u].productSum;
nd[pre].differenceSum += nd[u].differenceSum;
nd[pre].suc[1] = u; nd[u].isRoot = 0;
splay(u);
}
}
inline void link(int pre, int u)
{
access(pre); access(u);
ans += (double)(2 * nd[u].sz * nd[pre].productSum + sqr(nd[u].sz) * nd[pre].differenceSum) / sqr(n);
ans -= (double)nd[pre].a * sqr(nd[u].sz) / sqr(n);
nd[pre].tg += nd[u].sz; nd[pre].sz += nd[u].sz;
nd[pre].productSum += nd[u].sz * nd[pre].differenceSum;
nd[u].pre = pre;
nd[u].differenceSum -= nd[pre].a; nd[u].productSum -= (long long)nd[u].sz * nd[pre].a;
nd[u].lst = pre; nd[pre].bck.insert(u);
}
inline void cut(int u)
{
access(u);
ans += (double)(- 2 * nd[u].sz * nd[nd[u].suc[0]].productSum + sqr(nd[u].sz) * nd[nd[u].suc[0]].differenceSum) / sqr(n);
ans += (double)nd[nd[u].lst].a * sqr(nd[u].sz) / sqr(n);
nd[u].differenceSum = nd[u].a; nd[u].productSum = (long long)nd[u].a * nd[u].sz;
nd[nd[u].lst].bck.erase(nd[nd[u].lst].bck.find(u)); nd[u].lst = -1;
nd[nd[u].suc[0]].tg -= nd[u].sz; nd[nd[u].suc[0]].sz -= nd[u].sz;
nd[nd[u].suc[0]].productSum -= nd[u].sz * nd[nd[u].suc[0]].differenceSum;
nd[nd[u].suc[0]].pre = -1; nd[nd[u].suc[0]].isRoot = 1;
nd[u].suc[0] = -1;
}
inline void modify(int u, int x)
{
access(u);
int dlt = x - nd[u].a; nd[u].a = x;
ans += (double)dlt * sqr(nd[u].sz) / sqr(n);
nd[u].differenceSum += dlt; nd[u].productSum += (long long)nd[u].sz * dlt;
for(auto v : nd[u].bck)
{
splay(v); // 一定要先access, 否则没法保证之前的修改已经下传
ans -= (double)dlt * sqr(nd[v].sz) / sqr(n);
nd[v].differenceSum -= dlt; nd[v].productSum -= (long long)dlt * nd[v].sz;
}
}
inline int findRoot(int u) {while(! nd[u].isRoot) u = nd[u].pre; return u;}
}LCT;
int main()
{
#ifndef ONLINE_JUDGE
freopen("worn.in", "r", stdin);
freopen("worn.out", "w", stdout);
#endif
using namespace Zeonfai;
n = getInt(); ans = 0;
for(int i = 2; i <= n; ++ i) LCT.link(getInt(), i);
for(int i = 1; i <= n; ++ i) LCT.modify(i, getInt());
printf("%.9lf\n", ans);
int m = getInt();
for(int i = 0; i < m; ++ i)
{
int opt = getInt(), x = getInt(), y = getInt();
if(opt == 2) LCT.modify(x, y);
else
{
LCT.access(y);
int u = LCT.findRoot(x);
if(u == y) LCT.cut(y), LCT.link(x, y);
else LCT.cut(x), LCT.link(y, x);
}
printf("%.9lf\n", ans);
}
}