[分类讨论+线段树+BFS序]hdu5957: Query on a graph

题目大意

给你一张$N$个点$N$条边的无重边无自环的带权无向连通图,需要支持以下操作:

  • 操作一:对与结点$u$距离不超过$k$的点(包括$u$)的权值加上$d$。

  • 操作二:询问与结点$u$距离不超过$k$的点(包括$u$)的权值和。

初始权值为$0$,多组数据;

题解

这是一棵基环外向树,图上有且仅有一个环,每个环下面都挂了一棵树;

设$v[i]$为每个节点的权值,$son[i]$为节点$i$的儿子,$sson[i]$为节点$i$的孙子,$fa[i]$为节点$i$的父亲,$l[i]$为节点$i$在环上的邻居;

对于如何求答案,我们来分类讨论;

  1. $d=0,ans=v[u]$;

  2. $d=1​$;

    1. $u$在环上,$ans=v[u]+\sum v[son[u]]+\sum v[l[u]]$;
    2. $u$在树上,$ans=v[u]+\sum v[son[u]]+v[fa[u]]$;
  3. $d=2$;

    这里我们定义$Fa=fa[u]$,$L=l[u]$方便表示;

    1. $u$在环上,$ans=v[u]+\sum v[son[u]]+\sum v[sson[u]]+\sum v[l[u]]+\sum v[l[L]]+\sum v[son[L]]$;
    2. $u$在树上;
      1. $Fa$在环上,$ans=v[u]+\sum v[son[u]]+\sum v[sson[u]]+v[Fa]+\sum v[son[Fa]]+\sum v[l[Fa]]$
      2. $Fa$在树上,$ans=v[u]+\sum v[son[u]]+\sum v[sson[u]]+v[Fa]+v[fa[Fa]]+\sum v[son[Fa]]$

这里如果有重复的就不要再算;

修改同理;

这里如果暴力计算则需要$O(N^2)$的时间,所以我们想到一个东西叫$bfs$序;一个节点的儿子的$bfs$序是连续的,当然一个节点的孙子的$bfs$序也是连续的,于是就可以用线段树维护了;

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define SET 1,1,N
#define V(x) (Sum(SET,bfn[x],bfn[x]))
#define C(x,d) (Change(SET,bfn[x],bfn[x],d))
#define S(x) (Sum(SET,Lson[x],Rson[x]))
#define CS(x,d) (Change(SET,Lson[x],Rson[x],d))
using namespace std;
typedef long long ll;
inline void write(ll x){x<0?putchar('-'),x=-x:x=x;int num[100]={0};num[0]+=!x;while (x) num[++num[0]]=x%10,x/=10;for (int i=num[0];i;i--) putchar(num[i]+'0');puts("");}
inline int read(){
    int Res=0,f=1;char ch=getchar();
    while (ch>'9'||ch<'0') f=(ch=='-'?-f:f),ch=getchar();
    while (ch>='0'&&ch<='9') Res=Res*10+ch-'0',ch=getchar();
    return Res*f;
}
namespace MFS{
    int fa[100005];
    inline void init(int N){for (int i=1;i<=N;i++) fa[i]=i;}
    inline int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
    inline bool merge(int x,int y){x=getfa(x);y=getfa(y);if (x!=y) fa[x]=y;return x==y;}
}
int N,M;
int tot,lnk[100005],son[200005],nxt[200005],bfn[100005],fa[100005],bfs;
int Lson[100005],Rson[100005],Lsson[100005],Rsson[100005],LNeb[100005],RNeb[100005];
bool lop[100005];
bool DFS(int x,int End,int fa){
    if (x==End) return lop[x]=1;
    for (int i=lnk[x];i;i=nxt[i]){
        if (son[i]==fa) continue;
        if (DFS(son[i],End,x)) RNeb[x]=son[i],LNeb[son[i]]=x,lop[x]=1;
    }
    return lop[x];
}
inline void add(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
queue<int>Que;
struct ST{
    ll x,lazy;
}T[400005];
inline void pushdown(int x,int L,int R){
    ll &l=T[x].lazy;int mid=(L+R)>>1;
    if (l) T[x<<1].lazy+=l,T[x<<1|1].lazy+=l,T[x<<1].x+=l*(mid-L+1),T[x<<1|1].x+=l*(R-mid),l=0;
}
inline void Change(int p,int L,int R,int l,int r,int data){
    if (l==2e9||r==-2e9) return ;
    if (l<=L&&R<=r){T[p].lazy+=data;T[p].x+=data*(R-L+1);return ;}
    int mid=(L+R)>>1;pushdown(p,L,R);
    if (l<=mid) Change(p<<1,L,mid,l,r,data);
    if (mid<r) Change(p<<1|1,mid+1,R,l,r,data);
    T[p].x=T[p<<1].x+T[p<<1|1].x;
}
inline ll Sum(int p,int L,int R,int l,int r){
    if (l==2e9||r==-2e9) return 0;
    if (l<=L&&R<=r) return T[p].x;
    int mid=(L+R)>>1;pushdown(p,L,R);ll Res=0;
    if (l<=mid) Res+=Sum(p<<1,L,mid,l,r);
    if (mid<r) Res+=Sum(p<<1|1,mid+1,R,l,r);
    return Res;
}
inline ll calcNeb(int u,bool son,bool neb){
    ll val=V(LNeb[u])+V(RNeb[u]);
    if (son) if (LNeb[u]!=RNeb[u]) val+=S(LNeb[u])+S(RNeb[u]);else val+=S(LNeb[u]);
    if (neb){
        if (LNeb[LNeb[u]]==RNeb[u]) return val;
        if (LNeb[LNeb[u]]==RNeb[RNeb[u]]) return val+V(LNeb[LNeb[u]]);
        return val+V(LNeb[LNeb[u]])+V(RNeb[RNeb[u]]);
    }
    return val;
}
inline void changeNeb(int u,bool son,bool neb,int d){
    C(LNeb[u],d),C(RNeb[u],d);
    if (son) if (LNeb[u]!=RNeb[u]) CS(LNeb[u],d),CS(RNeb[u],d);else CS(LNeb[u],d);
    if (neb){
        if (LNeb[LNeb[u]]==RNeb[u]) return ;
        if (LNeb[LNeb[u]]==RNeb[RNeb[u]]) C(LNeb[LNeb[u]],d);
        else C(LNeb[LNeb[u]],d),C(RNeb[RNeb[u]],d);
    }
    return ;
}
int main()
{
    for (int t=read();t;t--){
        N=read();MFS::init(N);
        memset(lop,0,sizeof lop);bfs=0;
        memset(bfn,0,sizeof bfn);
        memset(fa,0,sizeof fa);
        memset(T,0,sizeof T);
        memset(LNeb,0,sizeof LNeb);
        memset(RNeb,0,sizeof RNeb);
        memset(lnk,0,sizeof lnk);tot=0;
        for (int i=1;i<=N;i++){
            int x=read(),y=read();
            if (MFS::merge(x,y)) LNeb[x]=y,RNeb[y]=x,DFS(x,y,0);
            add(x,y);add(y,x);Lson[i]=Lsson[i]=2e9;Rson[i]=Rsson[i]=-2e9;
        }
        for (int i=1;i<=N;i++) if (lop[i]) Que.push(i),bfn[i]=++bfs;
        while (Que.size()){
            int Now=Que.front();Que.pop();
            for (int i=lnk[Now];i;i=nxt[i]){
                if (bfn[son[i]]) continue;
                fa[son[i]]=Now;Que.push(son[i]);bfn[son[i]]=++bfs;
                Lson[Now]=min(Lson[Now],bfs);Lsson[fa[Now]]=min(Lsson[fa[Now]],bfs);
                Rson[Now]=max(Rson[Now],bfs);Rsson[fa[Now]]=max(Rsson[fa[Now]],bfs);
            }
        }
        M=read();
        for (int i=1;i<=M;i++){
            char ch[10];scanf("%s",ch);
            int op=ch[0]=='M',u=read(),k=read(),d;ll Ans=0;
            if (op==1){
                d=read();
                if (!k) C(u,d);
                if (k==1){
                    C(u,d);CS(u,d);
                    if (lop[u]) changeNeb(u,0,0,d);
                    else C(fa[u],d);
                }
                if (k==2){
                    CS(u,d);Change(SET,Lsson[u],Rsson[u],d);
                    if (lop[u]) C(u,d),changeNeb(u,1,1,d);
                    else{
                        C(fa[u],d);CS(fa[u],d);
                        if (lop[fa[u]]) changeNeb(fa[u],0,0,d);
                        else C(fa[fa[u]],d);
                    }
                }
            }
            else{
                if (!k) Ans=V(u);
                if (k==1){
                    Ans=V(u)+S(u);
                    if (lop[u]) Ans+=calcNeb(u,0,0);
                    else Ans+=V(fa[u]);
                }
                if (k==2){
                    Ans=S(u)+Sum(SET,Lsson[u],Rsson[u]);
                    if (lop[u]) Ans+=V(u),Ans+=calcNeb(u,1,1);
                    else {
                        Ans+=V(fa[u])+S(fa[u]);
                        if (lop[fa[u]]) Ans+=calcNeb(fa[u],0,0);
                        else Ans+=V(fa[fa[u]]);
                    }
                }
                write(Ans);
            }
        }
    }
    return 0;
}

发表评论

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