牛客挑战赛57C树上行走

牛客挑战赛57C树上行走

传送门

题目大意

给一棵\(n\)个点的树，每个点都有一个初始的权值\(a_i\)，有一个计数器\(b_i\)，初始值为\(0\)，现有两种操作：\(1、\)给定\(x,y\)，令\(x\rarr y\)的最短路上的点构成的序列为\(p\)，\(\forall i>1\)，\(b_{p_i}\)增加\(a_{p_{i-1}}\)；\(2、\)给定\(x\)，输出\(b_x\)的值。\((1\leq n\leq 5e5,1\leq q\leq 3e5,0\leq a_i\leq 1e9)\)

思路

很容易想到树链剖分，但是新手如我，之后就不会了。不过幸好，\(canon\)大佬给了一点思路。首先我们当然不可能暴力的去更新每一个点的值，那么我们可以发现能对一个点产生贡献的无非是它的父亲、重儿子和轻儿子，然后我们发现每个点的父亲和重儿子都最多只有一个，轻儿子可以有很多但是一棵树种轻儿子的数量一定是很少的，所以我们就可以通过暴力更新轻儿子的贡献，而对于父亲和重儿子的贡献我们可以通过建两个数组的方法来进行标记，询问的时候一起加上就可以了。而快速标记的方法无非线段树和树状数组，这两种方法都可以。

树状数组代码

#include
using namespace std;
int n,q;
vector>v(500005);
long long a[500005];
int dep[500005],siz[500005],son[500005],fa[500005];
int id[500005],top[500005],tot=0;
long long ans[500005];
int tree[2][500005];
inline int read()
{
    int s=0,w=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return (w==-1?-s:s);
}
void dfs(int x,int pre){
    siz[x]=1;
    dep[x]=dep[pre]+1;
    fa[x]=pre;
    for(auto to:v[x])if(to!=pre){
            dfs(to,x);
            siz[x]+=siz[to];
            if(siz[to]>siz[son[x]])son[x]=to;
        }
}
inline void dfs1(int x,int father)
{
    id[x]=++tot;
    if(son[x])
    {
        top[son[x]]=top[x];
        dfs1(son[x],x);
    }
    for(auto it:v[x])if(it!=father&&it!=son[x])
    {
        top[it]=it;
        dfs1(it,x);
    }
}
inline int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]

//现在搁这儿晾会儿，等我改好会更的哦~