BZOJ4372: 烁烁的游戏

BZOJ4372: 烁烁的游戏

https://lydsy.com/JudgeOnline/problem.php?id=4372

分析:

• 不是很难想的一道题，用树状数组维护点分树上每一层分治中心的点分序即可。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define N 100050
#define db(x) cerr<<#x<<" = "<<x<<endl
int n,m,head[N],to[N<<1],nxt[N<<1],cnt;
int siz[N],root,tot,fk[N],dep[N],dis[N][20],fa[N][20];
int used[N],bg[N][2],ed[N][2],satori,pos[N][20][2],c[N*40];
struct A {
    int x,d;
    A() {}
    A(int x_,int d_) {x=x_,d=d_;}
    bool operator < (const A &u) const {
        return d<u.d;
    }
}a[N*40];
inline void add(int u,int v) {
    to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;
}
void gr(int x,int y) {
    int i;
    siz[x]=1; fk[x]=0;
    for(i=head[x];i;i=nxt[i]) if(to[i]!=y&&!used[to[i]]) {
        gr(to[i],x); siz[x]+=siz[to[i]];
        fk[x]=max(fk[x],siz[to[i]]);
    }
    fk[x]=max(fk[x],tot-fk[x]);
    if(fk[x]<fk[root]) root=x;
}
void gd(int x,int y,int rt,int d) {
    int i;
    a[++satori]=A(x,d);
    a[satori+tot]=A(x,dis[x][dep[x]]);
    fa[x][++dep[x]]=rt;
    dis[x][dep[x]]=d;
    for(i=head[x];i;i=nxt[i]) if(to[i]!=y&&!used[to[i]]) {
        gd(to[i],x,rt,d+1);
    }
}
void solve(int x) {
    used[x]=1; int i;
    int all=tot;
    bg[x][0]=satori+1; ed[x][0]=satori+all;
    bg[x][1]=satori+all+1; ed[x][1]=satori+all+all;
    gd(x,0,x,0);
    satori+=all;
    sort(a+bg[x][0],a+ed[x][0]+1);
    sort(a+bg[x][1],a+ed[x][1]+1);
    for(i=bg[x][0];i<=ed[x][0];i++) {
        pos[a[i].x][dep[a[i].x]][0]=i;
    }
    for(i=bg[x][1];i<=ed[x][1];i++) {
        pos[a[i].x][dep[a[i].x]][1]=i;
    }
    for(i=head[x];i;i=nxt[i]) if(!used[to[i]]) {
        tot=siz[to[i]]; if(tot>siz[x]) tot=all-siz[x];
        root=0; gr(to[i],x); solve(root);
    }
}
void fix(int x,int o,int k,int v) {
    if(!x) return ;
    int b=bg[x][o],e=ed[x][o],l=b,r=e+1;
    while(l<r) {
        int mid=(l+r)>>1;
        if(a[mid].d<=k) l=mid+1;
        else r=mid;
    }
    l--;
    int t=l-b+1;
    for(;t;t-=t&(-t)) c[t+b]+=v;
}
int inq(int x,int o,int p) {
    int b=bg[x][o],e=ed[x][o],re=0;
    int t=p-b+1,lim=e-b+1;
    for(;t<=lim;t+=t&(-t)) re+=c[t+b]; 
    return re;
}
void update(int x,int k,int v) {
    int i;
    for(i=dep[x];i;i--) if(k>=dis[x][i]) {
        // db(fa[x][i]);
        fix(fa[x][i],0,k-dis[x][i],v);
        fix(fa[x][i+1],1,k-dis[x][i],-v);
    }
}
int query(int x) {
    int i,re=0;
    for(i=dep[x];i;i--) re+=inq(fa[x][i],0,pos[x][i][0])+inq(fa[x][i+1],1,pos[x][i+1][1]);
    return re;
}
char opt[10];
int main() {
    scanf("%d%d",&n,&m);
    int i,x,y;
    for(i=1;i<n;i++) {
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
    tot=n; fk[0]=1<<30; gr(1,0); solve(root);
    while(m--) {
        int k;
        scanf("%s%d",opt,&x);
        if(opt[0]=='M') {
            scanf("%d%d",&k,&y);
            update(x,k,y);
        }else {
            printf("%d\n",query(x));
        }
    }
}
/*
7 6
1 2
1 4
1 5
2 3
2 7
5 6
M 1 1 2
Q 5
M 2 2 3
Q 3
M 1 2 1
Q 2
*/

BZOJ4372: 烁烁的游戏

原文：https://www.cnblogs.com/suika/p/10164419.html