题解 | #树上行走#

题意

树上每个点有权值$a_{i}a\_i$和计数器$b_{i}b\_i$，维护两种操作：1.给定$x,yx,y$，对于x->y的路径形成序列p，对于$i>1i>1$，给$b_{p_i}+=a_{p_{i-1}}b\_\{p\_i\}+=a\_\{p\_\{i-1\}\}$ 2.询问$b_{x}b\_x$

分析

对于操作1，我们把路径分成$x->lcalca->yx->lca\; \backslash \; \backslash \; \backslash \; lca->y$两部分

对于第一部分，我们分别统计每个点来自重儿子和轻儿子的贡献

来自重儿子的可以利用树链剖分过程中的top，整体修改这一段都是重儿子的贡献

对于轻儿子的部分直接暴力加到b上即可

对于第二部分，每个人的贡献都来自父亲，是固定的，直接利用树剖+树状数组维护每个点有多少次父亲的贡献

复杂度$O(qlo{g}^{2}n)O(qlog^2n)$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+5;
int n,q;
vector <int> G[maxn];
ll a[maxn],b[maxn];
int dfn[maxn],siz[maxn],son[maxn];
int top[maxn],dep[maxn],f[maxn];
void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1;
    siz[u]=1; f[u]=fa;
    for(auto to:G[u])
    {
        if(to==fa) continue;
        dfs(to,u);
        siz[u]+=siz[to];
        if(siz[son[u]]<siz[to]) son[u]=to;
    }
}
int dfstime;
void dfss(int u,int fa)
{
    top[u]=fa; dfn[u]=++dfstime;
    if(son[u]) dfss(son[u],fa);
    for(auto to:G[u])
    {
        if(to==f[u] || to==son[u]) continue;
        dfss(to,to);
    }
}
int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]>dep[top[y]])
            x=f[top[x]];
        else y=f[top[y]];
    }
    return dep[x]<dep[y]?x:y;
}
int lowbit(int x)
{
    return x&(-x);
}
ll c1[maxn],c2[maxn];
ll query1(int x)
{
    ll res=0;
    while(x)
    {
        res+=c1[x];
        x-=lowbit(x);
    }
    return res;
}
ll query2(int x)
{
    ll res=0;
    while(x)
    {
        res+=c2[x];
        x-=lowbit(x);
    }
    return res;
}
void add1(int x,int y)
{
    while((x<=n || y<=n) && x!=y)
    {
        if(x<y) c1[x]++,x+=lowbit(x);
        else c1[y]--,y+=lowbit(y);
    }
}
void add2(int x,int y)
{
    while((x<=n || y<=n) && x!=y)
    {
        if(x<y) c2[x]++,x+=lowbit(x);
        else c2[y]--,y+=lowbit(y);
    }
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    int x,y;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1,0); dfss(1,1);
    for(int i=1;i<=q;i++)
    {
        int op; scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d",&x,&y);
            int z=lca(x,y);
            add2(dfn[y],dfn[z]);
            while(top[x]!=top[z])
            {
                add1(dfn[top[x]],dfn[x]);
                b[f[top[x]]]+=a[top[x]];
                x=f[top[x]];
            }
            add1(dfn[z],dfn[x]);
        }
        else
        {
            scanf("%d",&x);
            printf("%lld\n",b[x]+query1(dfn[x])*a[son[x]]+(query2(dfn[x]+siz[x]-1)-query2(dfn[x]-1))*a[f[x]]);
        }
    }
    return 0;
}