思路

比蓝题的树剖模板题少了一个函数...

不会树剖的可以看看洛谷日报以及oiwike.

代码

我复习了一下...
code大概有点长...

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5; 
int w[N];
vector<int>g[N];
int f[N],sz[N],son[N],dep[N];
void dfs(int u,int fa)
{
    sz[u]=1;dep[u]=dep[fa]+1;f[u]=fa;
    for(int v:g[u])
    {
        if(v==fa)    continue;
        dfs(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]])    son[u]=v;
    }
}

int dfn[N],idx[N],top[N],id;
void DFS(int u,int tp)
{
    dfn[u]=++id;
    idx[id]=u;
    top[u]=tp;
    if(!son[u])    return;
    DFS(son[u],tp);
    for(int v:g[u])
    {
        if(!dfn[v])
            DFS(v,v);
    }
}

struct SegTree{
    ll l,r,sum,lazy,len;
}tr[N<<2];

void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void pushdown(int u)
{
    tr[u<<1].sum+=tr[u<<1].len*tr[u].lazy;
    tr[u<<1|1].sum+=tr[u<<1|1].len*tr[u].lazy;
    tr[u<<1].lazy+=tr[u].lazy;
    tr[u<<1|1].lazy+=tr[u].lazy;
    tr[u].lazy=0;
}

void build(int u,int l,int r)
{
    tr[u].l=l,tr[u].r=r,tr[u].len=(r-l+1);
    if(l==r)
    {
        tr[u].sum=w[idx[l]];
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

void modify(int u,int L,int R,ll val)
{
    if(L>tr[u].r||R<tr[u].l)    return;
    if(L<=tr[u].l&&tr[u].r<=R)
    {
        tr[u].sum+=tr[u].len*val;
        tr[u].lazy+=val;
        return;
    }
    pushdown(u);
    modify(u<<1,L,R,val);
    modify(u<<1|1,L,R,val);
    pushup(u);
}

ll query(int u,int L,int R)
{
    if(L>tr[u].r||R<tr[u].l)    return 0;
    if(L<=tr[u].l&&tr[u].r<=R)
    {
        return tr[u].sum;
    }
    pushdown(u);
    return query(u<<1,L,R)+query(u<<1|1,L,R);
}

ll ask(int u,int v)//询问u到v的路径权值和.
{
    ll res=0;
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])    swap(u,v);
        res+=query(1,dfn[top[u]],dfn[u]);
        u=f[top[u]];
    }
    if(dep[u]<dep[v])    swap(u,v);
    res+=query(1,dfn[v],dfn[u]);
    return res;
} 

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u); 
    }
    dfs(1,1);
    DFS(1,1);
    build(1,1,n);
    while(m--)
    {
        int op,x,a;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d",&x,&a);//x节点权值+a 
            modify(1,dfn[x],dfn[x],a);
        }
        else if(op==2)
        {
            scanf("%d%d",&x,&a);//x的子树权值都+a.
            modify(1,dfn[x],dfn[x]+sz[x]-1,a); 
        }
        else
        {
            scanf("%d",&x);//询问x到根的权值和.
            printf("%lld\n",ask(1,x));
        }
    }
    return 0;
}