[JZOJ 5908] [NOIP2018模拟10.16] 开荒（kaihuang）解题报告（树状数组+思维）

题目链接：

https://jzoj.net/senior/#contest/show/2529/1

题目：

题目背景：
尊者神高达作为一个萌新，在升级路上死亡无数次后被一只大黄叽带回了师门。他加入师门后发现有无穷无尽的师兄弟姐妹，这几天新副本开了，尊者神高达的师门作为一个 pve师门，于是他们决定组织一起去开荒。

题目描述：
师门可以看做以 1 为根的一棵树，师门中的每一个人都有一定的装备分数。一共会有 q 个事件。每个事件可能是一次开荒，也可能是因为开荒出了好装备而导致一个人的装分出现了变化。对于一次开荒，会有 k 个人组织，由于师门的号召力很强，所以所有在组织者中任意两个人简单路径上的人都会参加。

题目大意：

在树上给出多个点，每次询问包含这些点的最小连通块的点权之和，带修改

题解：

对于每一个询问，我们把点按照dfs序从小到大排序。画个图我们发现，假设当前点为第i个点，第i个点的贡献就是从第i个点到与第i-1个点的LCA上的路径上的点权和，但是不包括LCA的点权。为什么不包括LCA的点权呢？发现其实我们从第1个点到最终的LCA上的点权和（这个要算上最终的LCA）都没有计算，最后一起计算就是了

为什么是对的呢？我们考虑到排名靠后的点要么在上一个点的子树里，要么就是新开一个子树。对于前者我们发现公共LCA不上移，直接计算到上一个点的路径和就是了，而事实上上一个点和这个点的LCA就是上一个点。对于后者我们发现公共LCA发生上移，这在最终的答案被我们统计了进去。

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;

typedef long long ll;

const int N=1e5+;

int n,Q,tot,tim;

int head[N],son[N],dep[N],fa[N][],dfn[N],id[N],sz[N],a[N];

ll val[N],t[N];

struct EDGE

{

    int to,nxt;

}edge[N<<];

inline ll read()

{

    char ch=getchar();

    ll s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

void link(int u,int v)

{

    edge[++tot]=(EDGE){v,head[u]};

    head[u]=tot;

}

void dfs(int x,int pre)

{

    sz[x]=;fa[x][]=pre;dfn[x]=++tim;id[tim]=x;

    for (int i=;i<;i++) fa[x][i]=fa[fa[x][i-]][i-];

    for (int i=head[x];i;i=edge[i].nxt)

    {

        int y=edge[i].to;

        if (y==pre) continue;

        dep[y]=dep[x]+;

        dfs(y,x);

        sz[x]+=sz[y];

    }

}

void add(int x,ll y)

{

    while (x<=n)

    {

        t[x]+=y;

        x+=x&-x;

    }

}

ll sum(int x)

{

    ll re=;

    while (x)

    {

        re+=t[x];

        x-=x&-x;

    }

    return re;

}

int lca(int x,int y)

{

    if (dep[x]<dep[y]) swap(x,y);

    for (int i=;i>=;i--) if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];

    if (x==y) return x;

    for (int i=;i>=;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];

    return fa[x][];

}

bool cmp(int a,int b){return dfn[a]<dfn[b];}

int main()

{

    freopen("kaihuang.in","r",stdin);

    freopen("kaihuang.out","w",stdout);

    n=read();Q=read();

    for (int i=;i<=n;i++) val[i]=read();

    for (int i=,u,v;i<n;i++)

    {

        u=read();v=read();

        link(u,v);link(v,u);

    }

    dep[]=;dfs(,);

    //for (int i=1;i<=n;i++) printf("%d ",sz[i]);

    //printf("\n");

    for (int i=;i<=n;i++)

    {

        add(dfn[i],val[i]);add(dfn[i]+sz[i],-val[i]);

    }

    char op[];

    for (int i=;i<=Q;i++)

    {

        scanf("%s",op);

        if (op[]=='C')

        {

            int x=read();ll y=read();

            add(dfn[x],-val[x]);add(dfn[x]+sz[x],val[x]);

            val[x]=y;

            add(dfn[x],y);add(dfn[x]+sz[x],-y);

        }

        if (op[]=='Q')

        {

            int k=;

            while ()

            {

                int x=read();

                if (!x) break;

                a[++k]=x;

            }

            sort(a+,a++k,cmp);

            if (k==)

            {

                printf("%lld\n",val[a[]]);

                continue;

            }

            ll re=sum(dfn[a[]]);int LCA=a[];

            for (int i=;i<=k;i++)

            {

                LCA=lca(LCA,a[i]);

                re+=sum(dfn[a[i]]);

                re-=sum(dfn[lca(a[i],a[i-])]);

            }

            re-=sum(dfn[fa[LCA][]]);

            printf("%lld\n",re);

        }

    }

    return ;

}

巴特西

[JZOJ 5908] [NOIP2018模拟10.16] 开荒（kaihuang）解题报告（树状数组+思维）

题目链接：

题目：

题目大意：

题解：

最新文章

热门文章

巴特西

[JZOJ 5908] [NOIP2018模拟10.16] 开荒（kaihuang）解题报告 （树状数组+思维）

题目链接：

题目：

题目大意：

题解：

最新文章

热门文章

[JZOJ 5908] [NOIP2018模拟10.16] 开荒（kaihuang）解题报告（树状数组+思维）