Tree Queries

· · 个人记录

Codeforces

水平有限，如有疏漏，墙裂欢迎提出
思路参考题解
算法标签：树链剖分

CF原题

简要题意： 给定一棵N个节点的树，有Q次操作

1：给定一个点v和一个权值d，等概率地选择一个点r，对每一个点u，若v在u到r的路径上，则u的权值加上d （权值一开始为0）

2： 查询v的权值期望，对998244353取模

①O(n\times q):

考虑对u点的贡献，若u在v子树内，则可以获得：d\times \frac{n-size_{u\text{所在子树}}}{n}

若u在v子树外，则可以获得：d\times \frac{size_v}{n}

如图：若v=6

$u=13$时，我们称$8$为$u$所在子树(对当前v来说)，除了$8$及其子树，其他点均可对$u$产生贡献 暴力修改每个点的期望 ②$O(q\times log(n))$: 考虑将单点操作变成区间操作，对于每一次询问： 若u在v子树外，就是在dfs序上的两段区间加 若u在v子树内： 问题出在无法快速求解$size_{u_\text{所在子树}}$，一点一点往上爬？时间复杂度会很糟糕；而如果我们**在一段连续的dfs序中默认了$u_\text{所在子树}$**，那么这一段就可以用"u在v子树外"情况的方法，区间加然后直接跳过了，对于**违背默认的**，仍采用朴素跳法 具体地，要实现**跳过一段连续的dfs序**并默认子树大小，这是树链剖分重链中可以维护的，而**违背默认**部分，实际上就是跳轻边的过程 $\color{Fuchsia}\text{Talk is Cheap, Show Me the Code!}

口胡谁都会，我要看代码

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int MAX=150004;
const int mod=998244353;
struct edge{
    int next,to;
}h[MAX<<1];
int head[MAX],cnt,cnt_dfsn;
int n,q,ans,inv;
inline void add(int x,int y){
    h[++cnt]=edge{head[x],y};
    head[x]=cnt;
    h[++cnt]=edge{head[y],x};
    head[y]=cnt;
}
int dfsn[MAX],size[MAX],son[MAX],fa[MAX],top[MAX],w[MAX];
int tree[MAX];   //差分
inline int lowbit(int x){
    return x&(-x);
}
inline void ad(int x,int y){
    y%=mod;
    for(int i=x;i<=n;i+=lowbit(i))tree[i]=(tree[i]+y)%mod;
}
inline int sum(int x){
    int ret=0;
    for(int i=x;i;i-=lowbit(i))ret=(ret+tree[i])%mod;
    return ret;
}
inline int quick(int x,int y){
    int ret=1ll;
    while(y){
        if(y&1)ret=(ret*x)%mod;
        y>>=1;
        x=(x*x)%mod;
    }
    return ret;
}
void dfs1(int now,int father){
    fa[now]=father;
    size[now]=1;
    for(int i=head[now];i;i=h[i].next){
        int aim=h[i].to;
        if(aim!=father){
            dfs1(aim,now);
            size[now]+=size[aim];
            if(size[aim]>size[son[now]])son[now]=aim;
        }
    }
}
void dfs2(int now,int start){
    top[now]=start;
    dfsn[now]=++cnt_dfsn;
    if(son[now])dfs2(son[now],start);
    for(int i=head[now];i;i=h[i].next){
        int aim=h[i].to;
        if(aim!=fa[now] && aim!=son[now]){
            dfs2(aim,aim);
        }
    }
}
signed main(){
    scanf("%lld %lld",&n,&q);
    inv=quick(n,mod-2);
    for(int x,y,i=1;i<n;i++)scanf("%lld %lld",&x,&y),add(x,y);
    dfs1(1,1),dfs2(1,1);
    fa[1]=0;
    for(int op,x,y,i=1;i<=q;i++){
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld %lld",&x,&y);    //指定点与权
            w[x]=(w[x]+y)%mod;
            //对外面询问的贡献
            ad(1,size[x]*y%mod);
            ad(dfsn[x],(mod-size[x]*y%mod)%mod),ad(dfsn[x]+size[x],size[x]*y%mod);
            //对内部(这里只修改本次通过重链爬上来的，轻边特判即可)
            if(son[x])ad(dfsn[son[x]],(n-size[son[x]])*y%mod),ad(dfsn[son[x]]+size[son[x]],mod-(n-size[son[x]])*y%mod);
        }else{
            scanf("%lld",&x);   //询问单点
            ans=(sum(dfsn[x])+n*w[x]%mod)%mod;
            for(int j=top[x];fa[j];j=top[fa[j]])ans=(ans+(n-size[j])*w[fa[j]]%mod)%mod;
            printf("%lld\n",(ans*inv)%mod);
        }
    }
    return 0;
}