题解 P4842 【城市旅行】

Wen_kr · 2018-12-03 09:53:35 · 题解

很有意思的一道题，看到还没有人发布题解我就发了...

ps : PoPoQQQ dalao Orz

涉及 Link 和 Cut,我们考虑使用 LCT。

对于一条路径：

a_1a_2a_3a_4\dots a_n

我们定义 a_i 为这条路径上第 i 个点的点权 (题目上的美丽程度)

那么设 exp 表示这条路径的期望，那么

exp = \frac{a_1*1*n+a_2*2*(n-1)+a_3*3*(n-2)+\dots+a_n*n*1}{C_n^2}

(洛咕不能用 cfrac 字体有点小，见谅)

这个式子怎么得来的呢？

我们首先考虑子路径条数，显然这个数字等于 C_n^2

对于第 i 个点的权值 a_i，它显然会被 i * (n - i + 1) 条路径覆盖(从 i 及 i 的左边选择左端点，从 i 及 i 的右边选择右端点)。

于是第 i 个点最后产生的贡献就是 a_i * i * (n - i + 1)

这些贡献累加起来就成了我们的分子。

分母我们在 split 之后只需要 sz 即可简单地算出，我们考虑在 splay 每个节点中维护分子。

怎样进行维护呢，我们考虑一条跨过根节点的路径长这样：

a_1 --- a_2 --- a_3 --- a_4(根节点) --- a_5 --- a_6

此时根节点部分维护的分子为 $a_1*1*6+a_2*2*5+a_3*3*4+\dots+a_6*6*1

左子树维护的分子为

a_1*1*3+a_2*2*2+a_3*3*1

左子树对当前节点的贡献应当为：

a_1*1*6+a_2*2*5+a_3*3*4

考虑两者做差，得到：

a_1*1*3+2_2*2*3+a_3*3*3 = 3*(a_1+2a_2+3a_3)

观察发现，外面的这个 3 恰好等于右子树的大小 + 1

我们设 lsum = a_1 * 1 + a_2 * 2 + a_3 * 3 + \dots + a_n * n

则左子树对答案的贡献为 exp_{lc}+lsum_{lc} * (sz_{rc}+1)

同理，我们设 rsum = a_1 * n + a_2 * (n - 1) + \dots + a_n * 1

那么右子树对答案的贡献为 exp_{rc}+rsum_{rc} * (sz_{lc} + 1)

还有根节点对答案的贡献，这个很好计算，就是：

val_{rt}*(sz_{lc}+1)*(sz_{rc}+1)

根节点的期望就可以计算了：

exp_{rt} = exp_{lc}+exp_{rc}+val_{rt}*(sz_{lc}+1)*(sz_{rc}+1)+

lsum_{lc} * (sz_{rc}+1)+rsum_{rc} * (sz_{lc} + 1)

我们设 $sum$ 表示当前子树内所有节点的权值和，那么 $lsum = lsum_{lc} + lsum_{rc} + sum_{rc} * (sz_{lc} + 1) + val_{rt} * (sz_{lc}+1)

rsum = rsum_{rc} + rsum_{lc} + sum_{lc} * (sz_{rc} + 1) + val_{rt} * (sz_{rc}+1)

这样，我们就解决了这个问题的一半：区间 Query

我们现在考虑更新。

假设我们给某个节点的子树的所有节点权值加上 p

那么显然地，

sum_{rt} = sum_{rt} + p * sz_{rt}

lsum_{rt} = lsum_{rt} + p * \frac{sz_{rt}*(sz_{rt}+1)}{2}

$val_{rt} = val_{rt} + p

然而 exp_{rt} 就很蛋疼了。

我们设 n = sz_{rt}

则exp_{rt} = exp_{rt} + p * (1 * n + 2 * (n - 1) + \dots + n * 1)

考虑重写 p 后面那一部分，我们能得到：

(1 + 2 + 3 + \dots + n) * n - (1 * 2 + 2 * 3 + \dots + (n - 1) * n)

前一部分很好化简，后面那一部分可以写成：

1^2+2^2+3^2+\cdots+(n-1)^2+1+2+\dots+(n-1)

根据小学奥数，这后半个式子整个等于:

\frac{n * (n + 1)}{2} * n - \frac{1}{6}*(n-1)*n*(2n-1)-\frac{n*(n-1)}{2}

然后开始化简，步骤如下:

\frac{n^3+n^2}{2}-\frac{2n^3-2n^2-n^2+n}{6}-\frac{n^2-n}{2}

\frac{3n^3+3n}{6}-\frac{2n^3-2n^2-n^2+n}{6}

\frac{n^3+3n^2+2n}{6}

\frac{n(n^2+3n+2)}{6}

\frac{n(n+1)(n+2)}{6}

这样我们就得到了更新的方法。

另外的，这道题 Push\_Down 必须当场 Push\_Down,否则会出问题(因为我们需要调用 lsum 和 rsum

最后，代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int son[50050][2],fa[50050],sz[50050];
long long lsum[50050],val[50050],rsum[50050],EXP[50050],sum[50050],upd_tag[50050];
int rev_tag[50050];

void Push_Up(int rt)
{
    sum[rt] = val[rt] + sum[son[rt][0]] + sum[son[rt][1]];
    sz[rt] = 1 + sz[son[rt][0]] + sz[son[rt][1]];
    lsum[rt] = lsum[son[rt][0]] + val[rt] * (sz[son[rt][0]] + 1) + lsum[son[rt][1]] + sum[son[rt][1]] * (sz[son[rt][0]] + 1);
    rsum[rt] = rsum[son[rt][1]] + val[rt] * (sz[son[rt][1]] + 1) + rsum[son[rt][0]] + sum[son[rt][0]] * (sz[son[rt][1]] + 1);
    EXP[rt] = EXP[son[rt][0]] + EXP[son[rt][1]] + val[rt] * (sz[son[rt][0]] + 1) * (sz[son[rt][1]] + 1) +
              lsum[son[rt][0]] * (sz[son[rt][1]] + 1) + rsum[son[rt][1]] * (sz[son[rt][0]] + 1);
}

void Rev(int rt)
{
    swap(son[rt][0],son[rt][1]);
    swap(lsum[rt],rsum[rt]);
    rev_tag[rt] ^= 1;
}

void Add(int rt,int valx)
{
    long long val1 = (sz[rt] * 1ll * (sz[rt] + 1)) / 2,val2 = (sz[rt] * 1ll * (sz[rt] + 1) * (sz[rt] + 2)) / 6;
    sum[rt] += valx * 1ll * sz[rt];
    val[rt] += valx;
    lsum[rt] += val1 * valx;
    rsum[rt] += val1 * valx;
    EXP[rt] += valx * val2;
    upd_tag[rt] += valx;
}

void Push_Down(int rt)
{
    if(rev_tag[rt])
    {
        Rev(son[rt][0]);
        Rev(son[rt][1]);
        rev_tag[rt] = 0;
    }
    if(upd_tag[rt])
    {
        Add(son[rt][0],upd_tag[rt]);
        Add(son[rt][1],upd_tag[rt]);
        upd_tag[rt] = 0;
    }
}

void Down(int rt)
{
    if(fa[rt]) Down(fa[rt]);
    Push_Down(rt);
}

bool is_root(int rt)
{
    return (son[fa[rt]][0] != rt && son[fa[rt]][1] != rt) || rt == 0;
}

void rotate(int rt)
{
    int f = fa[rt],g = fa[f];
    int way = son[f][1] == rt;
    if(!is_root(f)) son[g][son[g][1] == f] = rt;
    fa[rt] = g; son[f][way] = son[rt][way ^ 1];
    if(son[rt][way ^ 1]) fa[son[rt][way ^ 1]] = f;
    son[rt][way ^ 1] = f; fa[f] = rt;
    Push_Up(f); Push_Up(rt);
}

void splay(int rt)
{
    Down(rt);
    while(!is_root(rt))
    {
        int f = fa[rt],g = fa[f];
        if(!is_root(f)) (son[f][1] == rt) ^ (son[g][1] == rt) ? rotate(rt) : rotate(f);
        rotate(rt);
    }
}

void Access(int u)
{
    for(int v = 0;u;v = u,u = fa[u])
    {
        splay(u);
        son[u][1] = v;
        Push_Up(u);
    }
}

void make_root(int u)
{
    Access(u); splay(u); Rev(u);
}

int find_root(int u)
{
    Access(u); splay(u);
    while(son[u][0]) u = son[u][0];
    return u;
}

long long split(int u,int v)
{
    if(find_root(u) != find_root(v)) return -1;
    make_root(u); Access(v); splay(v);
    return EXP[v];
}

void Update(int u,int v,int val)
{
    if(find_root(u) != find_root(v)) return ;
    make_root(u); Access(v); splay(v);
    Add(v,val);
}

void Link(int u,int v)
{
    if(find_root(u) == find_root(v)) return ;
    make_root(u); fa[u] = v;
}

void Cut(int u,int v)
{
    if(find_root(u) != find_root(v)) return ;
    make_root(u); Access(v); splay(v);
    if(son[u][1] || son[v][0] != u) return;
    son[v][0] = fa[u] = 0;
    Push_Up(v);
}

long long gcd(long long a,long long b)
{
    return b == 0 ? a : gcd(b,a % b);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n; ++ i) scanf("%lld",&val[i]),Push_Up(i);
    for(int i = 1;i < n; ++ i)
    {
        int u,v;
        scanf("%d%d",&u,&v); Link(u,v);
    }
    for(int i = 1;i <= m; ++ i)
    {
        int op,u,v;scanf("%d%d%d",&op,&u,&v);
        int w; if(op == 3) scanf("%d",&w);
        if(op == 1) Cut(u,v);
        else if(op == 2) Link(u,v);
        else if(op == 3) Update(u,v,w);
        else
        {
            long long tmp = split(u,v);
            if(tmp == -1) printf("-1\n");
            else
            {
                long long csz = sz[v] * (sz[v] + 1) / 2;
                long long gcdx = gcd(csz,tmp);
                printf("%lld/%lld\n",tmp/gcdx,csz/gcdx);
            }
        }
    }
}