hihoCoder 1347 小h的树上的朋友

时间限制:18000ms
单点时限:2000ms
内存限制:512MB

描述

小h拥有$n$位朋友。每位朋友拥有一个数值$V_i$代表他与小h的亲密度。亲密度有可能发生变化。
岁月流逝，小h的朋友们形成了一种稳定的树状关系。每位朋友恰好对应树上的一个节点。
每次小h想请两位朋友一起聚餐，他都必须把连接两位朋友的路径上的所有朋友都一起邀请上。并且聚餐的花费是这条路径上所有朋友的亲密度乘积。
小h很苦恼，他需要知道每一次聚餐的花销。小h问小y，小y当然会了，他想考考你。

输入

输入文件第一行是一个整数 $n$，表示朋友的数目，从 $1$ 开始编号。
输入文件第二行是 $n$ 个正整数 $V_i$，表示每位朋友的初始的亲密度。
接下来 $n-1$ 行，每行两个整数 $u$ 和 $v$，表示 $u$ 和 $v$ 有一条边。
然后是一个整数 $m$，代表操作的数目。每次操作为两者之一：
$0 u v$ 询问邀请朋友 $u$ 和 $v$ 聚餐的花费

$1 u v$ 改变朋友 $u$ 的亲密度为 $v$

$1le n,mle 5 imes 10^5$

$V_ile 10^9$

输出

对于每一次询问操作，你需要输出一个整数，表示聚餐所需的花费。你的答案应该模 $1,000,000,007$ 输出。
样例输入

    3
    1 2 3
    1 2
    2 3
    5
    0 1 2
    0 1 3
    1 2 3
    1 3 5
    0 1 3

样例输出

    2
    6
    15

Solution

比较裸的做法是树链剖分，我试了一发，但这题数据较大，会TLE ，不过据说LCT可以水过，然而我不会LCT。

正解：DFS序 + 树状数组/线段树，询问和更新复杂度都是 $O(log{n})$。

对节点 $u$，将根节点到 $u$ 的路径上的点的权值之积维护成前缀积，记作 $pro[u]$。

显然 $u$ 到 $v$ 路径上节点的权值之积可表示为：

[dfrac{pro[u] imes pro[v] imes a[lca(u, v)]}{(pro[lca(u, v)])^2},]

上式中 $a[x]$ 表示节点 $x$ 的权值。

不过我一开始把这个式子搞错了:

[dfrac{pro[u] imes pro[v]}{pro[lca(u, v)]}]

WA了N发，真是太SB了。。。

其他的坑点：

连乘时要边乘边模，否则会爆long long。

教训：

调用函数时要留意一下参数类型。

Implementation

#include <bits/stdc++.h>
using namespace std;

const int N{1<<19}, M(1e9+7);
typedef long long LL;

LL bit[N];
int n;

LL pro(int x){
    LL res=1;
    for(; x; res=res*bit[x]%M, x-=x&-x);
    return res;
}

void mul(int x, int v){
    for(; x&&x<=n; bit[x]=bit[x]*v%M, x+=x&-x);
}

LL Pow(LL x, int n){
    LL res=1;
    for(; n; x*=x, x%=M, n>>=1)
        if(n&1) res*=x, res%=M;
    return res;
}

LL inv(int x){
    return Pow(x, M-2);
}

int a[N], tail, fa[N][19], dep[N], L[N], R[N];
vector<int> g[N];

void dfs(int u, LL p, int f){
    fa[u][0]=f, dep[u]=dep[f]+1;
    for(int i=1; i<19; i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    L[u]=++tail;
    mul(tail, inv(pro(tail-1))*p%M);
    for(auto &v:g[u])
        if(v!=f) dfs(v, p*a[v]%M, u);
    R[u]=tail;
}

int LCA(int u, int v){
    if(dep[u]<dep[v]) swap(u, v);
    int diff=dep[u]-dep[v];
    for(int i=0; i<19; i++)
        if(diff&1<<i) u=fa[u][i];
    if(u==v) return u;
    for(int i=18; i>=0; i--)
        if(fa[u][i] != fa[v][i]) u=fa[u][i], v=fa[v][i];
    return fa[u][0];
}

int main(){
    cin>>n;
    for(int i=1; i<=n; i++)
        scanf("%d", a+i), bit[i]=1;

    for(int u, v, i=1; i<n; i++)
        scanf("%d%d", &u, &v), g[u].push_back(v), g[v].push_back(u);
    dfs(1, a[1], 0);

    int m; cin>>m;
    for(int t, u, v; m--; ){
        scanf("%d%d%d", &t, &u, &v);
        if(t==0){
            int w=LCA(u, v);
            LL t=pro(L[w]);
            LL res=pro(L[u])*pro(L[v])%M*inv(t*t%M)%M*a[w]%M;
            printf("%lld
", res);    //error-prone
        }
        else{
            mul(L[u], inv(a[u])*v%M), mul(R[u]+1, a[u]*inv(v)%M), a[u]=v;    //error-prone
        }
    }
}