牛客挑战赛57C树上行走

本文主要是介绍牛客挑战赛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<bits/stdc++.h>
using namespace std;
int n,q;
vector<vector<int>>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];
long long tree[2][500005];
void dfs(int x,int father)
{
    siz[x]=1;
    dep[x]=dep[father]+1;
    int maxsize=0;
    for(auto it:v[x])if(it!=father)
    {
        fa[it]=x;
        dfs(it,x);
        siz[x]+=siz[it];
        if(siz[it]>maxsize)
        {
            maxsize=siz[it];
            son[x]=it;
        }
    }
}
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);
    }
}
int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])return x;
    else return y;
}
void update(int x,int w,int op)
{
    while(x<=500005)
    {
        tree[op][x]+=w;
        x+=(x&-x);
    }
}
int query(int x,int op)
{
    int sum=0;
    while(x)
    {
        sum+=tree[op][x];
        x-=(x&-x);
    }
    return sum;
}
void Update1(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(top[x]!=x)
        {
            update(id[top[x]],1,0);
            update(id[fa[x]]+1,-1,0);
        }
        x=top[x];
        ans[fa[x]]+=a[x];
        x=fa[x];
    }
    if(x!=y)
    {
        update(id[y],1,0);
        update(id[fa[x]]+1,-1,0);
    }
}
void Update2(int x,int y)
{
    while(top[x]!=top[y])
    {
        update(id[top[y]],1,1);
        update(id[y]+1,-1,1);
        y=fa[top[y]];
    }
    update(id[x]+1,1,1);
    update(id[y]+1,-1,1);
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<n;i++)
    {
        int from,to;
        scanf("%d%d",&from,&to);
        v[from].push_back(to);
        v[to].push_back(from);
    }
    dfs(1,0);
    top[1]=1;
    dfs1(1,0);
    while(q--)
    {
        int op;
        scanf("%d",&op);
        if(op==1)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int Lca=lca(x,y);
            if(x!=Lca)Update1(x,Lca);
            if(y!=Lca)Update2(Lca,y);
        }
        else
        {
            int x;
            scanf("%d",&x);
            long long ans1=ans[x];
            if(son[x])ans1+=a[son[x]]*query(id[x],0);
            if(fa[x])ans1+=a[fa[x]]*query(id[x],1);
            printf("%lld\n",ans1);
        }
    }
    return 0;
}

线段树代码

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

这篇关于牛客挑战赛57C树上行走的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！