题目概述

给一棵基环树，有两种操作：1.将到 $x$ 的距离 $\le K$ 的点权值均加上 $d$ 。2.询问到 $x$ 距离 $\le K$ 的点的权值和。

解题报告

emm……DFS序做多了都忘了还有个BFS序了……由于是基环树所以先找出环，然后从环的节点出发做BFS得到每个点儿子所在的区间以及孙子所在的区间，因为是BFS序所以肯定是连续的。

用线段树维护权值和，然后就是疯狂的讨论……

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000;

int T,n,te,a[maxn+5],fa[maxn+5],BCC[maxn+5];bool vis[maxn+5];char s[10];
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];
int que[maxn+5],ti,ID[maxn+5],Ls[maxn+5],Rs[maxn+5],Lg[maxn+5],Rg[maxn+5];
int l[(maxn<<2)+5],r[(maxn<<2)+5],tag[(maxn<<2)+5];LL sum[(maxn<<2)+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
inline void getBCC(int x,int y) {for (int i=x;i!=y;i=fa[i]) a[++a[0]]=i,BCC[i]=a[0];a[++a[0]]=y;BCC[y]=a[0];}
void Dfs(int x,int pre=0){
    for (int j=(vis[x]=true,lnk[x]);j;j=nxt[j])
        if (son[j]!=pre) if (!vis[son[j]]) fa[son[j]]=x,Dfs(son[j],x); else if (!BCC[x]) getBCC(x,son[j]);
}
void Bfs(int S){
    int Head=0,Tail=0;ID[que[++Tail]=S]=++ti;vis[S]=true;
    while (Head!=Tail){
        int x=que[++Head];Ls[x]=ti+1;
        for (int j=lnk[x];j;j=nxt[j])
            if (!ID[son[j]]&&!BCC[son[j]]) fa[son[j]]=x,ID[que[++Tail]=son[j]]=++ti,vis[son[j]]=true;Rs[x]=ti;
    }
    for (int i=1;i<=Tail;i++){
        int x=que[i];Lg[x]=2e9;Rg[x]=-2e9;
        for (int j=lnk[x];j;j=nxt[j])
            if (ID[son[j]]>ID[x]&&!BCC[son[j]]) Lg[x]=min(Lg[x],Ls[son[j]]),Rg[x]=max(Rg[x],Rs[son[j]]);
    }
}
void Build(int L,int R,int p=1){
    tag[p]=0;l[p]=L;r[p]=R;sum[p]=0;if (L==R) return;int mid=L+(R-L>>1);
    Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);
}
#define Pushup(p) (sum[p]=sum[(p)<<1]+sum[(p)<<1|1])
inline void Addtag(int p,int k) {sum[p]+=(LL)(r[p]-l[p]+1)*k;tag[p]+=k;}
inline void Pushdown(int p) {if (tag[p]) Addtag(p<<1,tag[p]),Addtag(p<<1|1,tag[p]),tag[p]=0;}
void Insert(int L,int R,int k,int p=1){
    if (R<l[p]||r[p]<L) return;if (L<=l[p]&&r[p]<=R) return Addtag(p,k);int mid=l[p]+(r[p]-l[p]>>1);
    Pushdown(p);if (R<=mid) Insert(L,R,k,p<<1); else if (L>mid) Insert(L,R,k,p<<1|1);
    else Insert(L,mid,k,p<<1),Insert(mid+1,R,k,p<<1|1);Pushup(p);
}
LL Ask(int L,int R,int p=1){
    if (R<l[p]||r[p]<L) return 0;if (L<=l[p]&&r[p]<=R) return sum[p];int mid=l[p]+(r[p]-l[p]>>1);
    Pushdown(p);if (R<=mid) return Ask(L,R,p<<1);if (L>mid) return Ask(L,R,p<<1|1);
    return Ask(L,mid,p<<1)+Ask(mid+1,R,p<<1|1);
}
#define Pre(x) ((x)>1?(x)-1:a[0])
#define Suf(x) ((x)<a[0]?(x)+1:1)
inline void Update(int x,int K,int w){
    if (K>=0) Insert(ID[x],ID[x],w);
    if (K>=1) if (Insert(Ls[x],Rs[x],w),!BCC[x]) Insert(ID[fa[x]],ID[fa[x]],w);
    else Insert(ID[a[Pre(BCC[x])]],ID[a[Pre(BCC[x])]],w),Insert(ID[a[Suf(BCC[x])]],ID[a[Suf(BCC[x])]],w);
    if (K>=2) if (Insert(Lg[x],Rg[x],w),!BCC[x]){
        if (Insert(ID[x],ID[x],-w),Insert(Ls[fa[x]],Rs[fa[x]],w),!BCC[fa[x]]) Insert(ID[fa[fa[x]]],ID[fa[fa[x]]],w);
        else {int p=BCC[fa[x]];Insert(ID[a[Pre(p)]],ID[a[Pre(p)]],w);Insert(ID[a[Suf(p)]],ID[a[Suf(p)]],w);}
    } else{
        int L=Pre(BCC[x]),R=Suf(BCC[x]);Insert(Ls[a[L]],Rs[a[L]],w);Insert(Ls[a[R]],Rs[a[R]],w);
        if (Pre(L)!=L&&Pre(L)!=R) Insert(ID[a[Pre(L)]],ID[a[Pre(L)]],w);
        if (Suf(R)!=L&&Suf(R)!=R&&Suf(R)!=Pre(L)) Insert(ID[a[Suf(R)]],ID[a[Suf(R)]],w);
    }
}
inline LL Query(int x,int K){LL ans=0;
    if (K>=0) ans+=Ask(ID[x],ID[x]);
    if (K>=1) if (ans+=Ask(Ls[x],Rs[x]),!BCC[x]) ans+=Ask(ID[fa[x]],ID[fa[x]]);
    else ans+=Ask(ID[a[Pre(BCC[x])]],ID[a[Pre(BCC[x])]]),ans+=Ask(ID[a[Suf(BCC[x])]],ID[a[Suf(BCC[x])]]);
    if (K>=2) if (ans+=Ask(Lg[x],Rg[x]),!BCC[x]){
        if (ans-=Ask(ID[x],ID[x]),ans+=Ask(Ls[fa[x]],Rs[fa[x]]),!BCC[fa[x]]) ans+=Ask(ID[fa[fa[x]]],ID[fa[fa[x]]]);
        else {int p=BCC[fa[x]];ans+=Ask(ID[a[Pre(p)]],ID[a[Pre(p)]]);ans+=Ask(ID[a[Suf(p)]],ID[a[Suf(p)]]);}
    } else{
        int L=Pre(BCC[x]),R=Suf(BCC[x]);ans+=Ask(Ls[a[L]],Rs[a[L]]);ans+=Ask(Ls[a[R]],Rs[a[R]]);
        if (Pre(L)!=L&&Pre(L)!=R) ans+=Ask(ID[a[Pre(L)]],ID[a[Pre(L)]]);
        if (Suf(R)!=L&&Suf(R)!=R&&Suf(R)!=Pre(L)) ans+=Ask(ID[a[Suf(R)]],ID[a[Suf(R)]]);
    }return ans;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d",&T);T;T--){E=0;memset(lnk,0,sizeof(lnk));memset(BCC,0,sizeof(BCC));memset(vis,0,sizeof(vis));
        scanf("%d",&n);for (int i=1,x,y;i<=n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);a[0]=0;Dfs(1);
        memset(vis,0,sizeof(vis));memset(ID,0,sizeof(ID));ti=0;for (int i=1;i<=a[0];i++) Bfs(a[i]);Build(1,ti);
        for (int x=scanf("%d",&te),y,z;te;te--){
            if (scanf("%s%d%d",s,&x,&y),s[0]=='Q') printf("%lld\n",Query(x,y));
            else scanf("%d",&z),Update(x,y,z);
        }
    }return 0;
}