正题

题目链接:https://www.luogu.com.cn/problem/P6329

解题思路

给出\(n\)个点的一棵树，每个点有权值，有\(m\)次操作

修改一个点\(x\)的权值为\(y\)
询问距离点\(x\)不超过\(k\)的所有点点权和

解题思路

点分树的模板题，先点分治构造出点分树，然后在上面维护信息。

对于每个点维护一个点分子树内，与该点的距离为下标，点权为权值的的树状数组，然后查询的时候直接查距离不超过\(k-dis(now,x)\)的就好了。

发现与点分父节点会有算重的情况，这个时候顺便维护一个以与父节点的距离为下标的树状数组，然后减去重复的答案就好了。

时间复杂度\(O(n\log^2 n)\)。

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define lowbit(x) (x&-x)

using namespace std;

const int N=1e5+10,T=18,inf=1e9;

struct node{

    int to,next;

}a[N<<1];

int n,m,tot,cnt,num,root,fr,val[N];

int ls[N],f[N<<1][T],rfn[N],dep[N];

int fa[N],siz[N],lg[N<<1],mx;

bool v[N];

struct BIT{

    vector<int> t;int n;

    void Init(int x)

    {x++;t.resize(x);n=x;return;}

    void Change(int x,int val){

        x++;

        while(x<=n){

            t[x-1]+=val;

            x+=lowbit(x);

        }

        return;

    }

    int Ask(int x){

        if(x<0)return 0;

        int ans=0;x++;

        if(x>n)x=n;

        while(x){

            ans+=t[x-1];

            x-=lowbit(x);

        }

        return ans;

    }

}s1[N],s2[N];

void addl(int x,int y){

    a[++tot].to=y;

    a[tot].next=ls[x];

    ls[x]=tot;return;

}

void dfs(int x,int fa){

    dep[x]=dep[fa]+1;

    f[++cnt][0]=x;rfn[x]=cnt;

    for(int i=ls[x];i;i=a[i].next){

        int y=a[i].to;

        if(y==fa)continue;

        dfs(y,x);f[++cnt][0]=x;

    }

    return;

}

void groot(int x,int fa){

    siz[x]=1;int f=0;

    for(int i=ls[x];i;i=a[i].next){

        int y=a[i].to;

        if(v[y]||y==fa)continue;

        groot(y,x);siz[x]+=siz[y];

        f=max(f,siz[y]);

    }

    f=max(f,num-siz[x]);

    if(f<fr)root=x,fr=f;

    return;

}

void calc(int x,int fa,int dep){

    mx=max(mx,dep);

    for(int i=ls[x];i;i=a[i].next){

        int y=a[i].to;

        if(y==fa||v[y])continue;

        calc(y,x,dep+1);

    }

    return;

}

void Build(int x,int h){

    v[x]=1;int S=num,z=fr;

    mx=0;calc(x,x,0);

    s1[x].Init(mx);

    s2[x].Init(h);

    for(int i=ls[x];i;i=a[i].next){

        int y=a[i].to;

        if(v[y])continue;

        num=(siz[y]>siz[x])?(S-siz[x]):siz[y];

        mx=0;calc(y,x,1);

        fr=inf;groot(y,x);y=root;fa[y]=x;

        Build(y,mx);

    }

    return;

}

void Init(){

    dfs(1,1);

    for(int i=2;i<=cnt;i++)lg[i]=lg[i>>1]+1;

    for(int j=1;(1<<j)<=cnt;j++)

        for(int i=1;i+(1<<j)-1<=cnt;i++){

            int x=f[i][j-1],y=f[i+(1<<j-1)][j-1];

            f[i][j]=(dep[x]<dep[y])?x:y;

        }

    fr=inf;num=n;groot(1,1);

    Build(root,0);

    return;

}

int LCA(int l,int r){

    l=rfn[l];r=rfn[r];

    if(l>r)swap(l,r);

    int z=lg[r-l+1];

    int x=f[l][z],y=f[r-(1<<z)+1][z];

    return (dep[x]<dep[y])?x:y;

}

int dis(int x,int y)

{return dep[x]+dep[y]-2*dep[LCA(x,y)];}

void Updata(int x,int val){

    int now=x;

    while(now){

        s1[now].Change(dis(now,x),val);

        if(fa[now])s2[now].Change(dis(fa[now],x),val);

        now=fa[now];

    }

    return;

}

int Ask(int x,int k){

    int ans=0,now=x;

    ans=s1[x].Ask(k);

    while(fa[now]){

        int d=dis(fa[now],x);

        ans+=s1[fa[now]].Ask(k-d);

        if(fa[now])ans-=s2[now].Ask(k-d);

        now=fa[now];

    }

    return ans;

}

int main()

{

    // freopen("P6329_1.in","r",stdin);

    // freopen("data.out","w",stdout);

    scanf("%d%d",&n,&m);

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

        scanf("%d",&val[i]);

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

        int x,y;

        scanf("%d%d",&x,&y);

        addl(x,y);addl(y,x);

    }

    Init();

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

        Updata(i,val[i]);

    int last=0;

    while(m--){

        int op,x,y;

        scanf("%d%d%d",&op,&x,&y);

        x^=last;y^=last;

        if(op){

            Updata(x,y-val[x]);

            val[x]=y;

        }

        else

            printf("%d\n",last=Ask(x,y));

    }

    return 0;

}

巴特西

P6329-[模板]点分树 | 震波

正题

解题思路

解题思路

code

最新文章

热门文章