虚树小讲

起因:

因为今天有一道题可以用虚树做,然后我边上的yjc大佬又正好是是用虚树写的,我就顺便学了一下,现在来讲一讲…..

题目:

尊者神高达作为一个萌新,在升级路上死亡无数次后被一只大黄叽带回了师门。他加入师门后发现有无穷无尽的师兄弟姐妹,这几天新副本开了,尊者神高达的师门作为一个pve师门,于是他们决定组织一起去开荒
师门可以看做以1为根的一棵树,师门中的每一个人都有一定的装备分数。一共会有q个事件。每个事件可能是一次开荒,也可能是因为开荒出了好装备而导致一个人的装分出现了变化。对于一次开荒,会有k个人组织,由于师门的号召力很强,所以所有在组织者中任意两个人简单路径上的人都会参加。

输入格式:

第一行n,q;
接下来1行n个数,代表每个人的分值;
接下来n~1uv代表一条边
接下来qQ 代表询问,接下来k个数代表组织的人数,读入为0时停止读入。
C代表修改,输入x,w代表将x的分值变为w

数据范围:

所有数据n,q<=100000,所有询问k的和<=1000000,w<=1e7
保证数据合法

分析:

我们先来讲一讲虚树是做什么的….
我们知道有些题目:给定一棵树,另有多次询问,每个询问给定一些关键点,需要求这些关键点之间的某些信息。询问数可能很多,但满足所有询问中关键点数量的总和与树的大小同阶。
这样的问题由于询问特别多,然后每次询问的点却不多,每次遍历整棵树是会TLE的,那么这个时候就可以引进一种树,叫虚树…
虚树是原树的一颗简化版,他包含了所有询问点和他们的lca,易得虚树上点的数量不会超过询问点的2倍….
有一个树:
1\to2;2\to3;2\to4
我们询问3,4点,那么这棵树的虚树就变成了:
2\to3;2\to4
也就是说询问点中任意两的点的lca均在虚树中…
然后我们把那些省略掉的点变成边的权值存了起来,这样子我们遍历的时候就会减少要跑的点……
然后我们考虑如何建虚树….
首先我们要现将询问点按照dfs序排序…这样保证依次加入的点要么在之前点的子树内,要么是祖先的兄弟…..
然后我们用栈来维护虚树上的一天右链 ,为什么是右链呢….
我们发现虚树的左链不会对后面加入的点产生影想,因为后加入的点都在右链的右边….
然后我们考虑新加入的一个点q,此时存链栈顶的元素是p,
1. 有LCA=lca(q,p);如果LCA的dfs序和p相同就可以直接加入q;
2. 如果LCA的dfs序在p之前说明在加入这个节点以后p变成了一条左链,那么q不会和他相连,那么我们在弹出他时,就可以在ans上加上p到栈顶第二个元素的链的值….重复操作直到p的dfs序在LCA值前(前面最后一次弹出操作,更新的值是p到LCA的链),如果栈顶不是LCA那么我们加入LCA然后加入q,否则直接加入q

因为我们更新ans,是在弹出时进行的,所以还要加上最后栈里的那条链;
然后虚树就建好了…..
对于上面这道题目,我们可以用一个树状数组维护单点修改,因为一个点改动那么他子树内的所有点也会改动,用树状数组就可以进行log级别的修改操作,然后对于每一次询问我们都构建一棵新的虚树,统计答案即可…..

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define LL long long
#define int LL
#define P pair<int,int>
const LL inf=1e9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,q;
int cost[400010];
int head[400010],cnt;
struct Edge{int next,to;}edge[200010];
inline void add(int from,int to)
{
    edge[++cnt].to=to;
    edge[cnt].next=head[from];
    head[from]=cnt;
}
int fa[400010][22],dep[400010];
int be[400010],en[400010],num;
LL C[400010],tr[400010];
void dfs(int now,int fath)
{
    be[now]=++num;dep[now]=dep[fath]+1;
    fa[now][0]=fath;C[now]=C[fa[now][0]]+cost[now];
    for(int j=1;j<=20;j++)
        fa[now][j]=fa[fa[now][j-1]][j-1];
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fath) continue;
        dfs(to,now);
    }en[now]=num;
}
int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--)
        if(dep[fa[x][i]]>=dep[y])
            x=fa[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int xx[100000],tot,ans;stack<int> vtree;
void add_cost(int x,int c){for(int i=x;i<=n;i+=i&-i)tr[i]+=c;}
void change(int l,int r,int c) {add_cost(l,c),add_cost(r+1,-c);}
int query(int x,int ret=0){for(int i=x;i;i-=i&-i) ret+=tr[i];return ret;}
bool cmp(int a,int b){return be[a]<be[b];}
signed main()
{
    read(n),read(q);
    for(int i=1;i<=n;i++) read(cost[i]);
    for(int i=1,u,v;i<n;i++) read(u),read(v),add(u,v),add(v,u);
    C[1]=cost[1];dfs(1,0);
    for(int i=1;i<=n;i++)
        change(be[i],be[i],C[i]);
    for(int cas=1;cas<=q;cas++)
    {
        char s[10];scanf("%s",s);
        if(s[0]=='C')
        {
            int x,y;
            read(x),read(y);
            change(be[x],en[x],y-query(be[x])+query(be[fa[x][0]]));
        }
        else 
        {
            ans=0;tot=0;
            while(scanf("%lld",&xx[++tot])&&xx[tot]);tot--;
            sort(xx+1,xx+tot+1,cmp);
            vtree.push(xx[1]);
            for(int i=2;i<=tot;++i)
            {
                int LCA=lca(vtree.top(),xx[i]),x;
                for(;!vtree.empty()&&be[vtree.top()]>be[LCA];vtree.pop())x=vtree.top();
                if(vtree.empty())ans+=query(be[x])-query(be[LCA]);
                if(vtree.empty()||vtree.top()!=LCA)vtree.push(LCA);
                vtree.push(xx[i]);ans+=query(be[xx[i]])-query(be[LCA]);
            }
            int x=0;
            for(;!vtree.empty();vtree.pop())x=vtree.top();
            printf("%lld\n",ans+query(be[x])-query(be[fa[x][0]]));
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注