OrzFAng系列–树 解题报告

题目描述

方方方种下了三棵树，两年后，第二棵树长出了n个节点，其中1号节点是根节点。

给定一个n个点的树

支持两种操作

方方方进行m次操作，每个操作为：

（1）给出两个数i，x，将第i个节点的子树中，与i距离为斐波那契数的节点权值+x（包括i本身）。

（2）给出一个数i，求出第i个节点的子树中，与i距离为斐波那契数的节点的权值和（包括i本身）。

题解

斐波那契数列

首先这个会被操作的只有大概25层的节点。

这样深度相同的区间在bfs序上是连续的区间，那么只要求出这样的左右端点是哪些，后面的就可以建个线段树|树状数组维护

原来我觉得这样的区间很难求。其实只要类似倍增的做法表示i的次祖先。就可以直接求了。

bfs序上的区间修改/查询 还可以用bit

这类的玩意http://www.cnblogs.com/zzqsblog/p/5692627.html

#include<map>

#include<stack>

#include<queue>

#include<cstdio>

#include<string>

#include<vector>

#include<cstring>

#include<complex>

#include<iostream>

#include<assert.h>

#include<algorithm>

using namespace std;

#define inf 1001001001

#define infll 1001001001001001001LL

#define ll long long

#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl

#define gmax(a,b) (a)=max((a),(b))

#define gmin(a,b) (a)=min((a),(b))

#define Ri register int

#define gc getchar()

#define il inline

il int read(){

    bool f=true;Ri x=;char ch;while(!isdigit(ch=gc))if(ch=='-')f=false;while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=gc;}return f?x:-x;

}

#define gi read()

#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);

struct edge{

    int to,next;

}e[];

int last[],dep[],val[],f[][],cnt,n,m;

ll sum;

il void link(int a,int b){

    e[++cnt]=(edge){b,last[a]};last[a]=cnt;

    e[++cnt]=(edge){a,last[b]};last[b]=cnt;

}

int lf[][],rf[][],bfn[],_bfn;

// i的fib_i层的左&右

void dfs(int x,int fa=){

    dep[x]=dep[fa]+;

    f[x][]=f[x][]=fa;

    for(int i=;i<=;i++)f[x][i]=f[f[x][i-]][i-];

    for(int i=last[x];i;i=e[i].next){

        if(e[i].to!=fa){

            dfs(e[i].to,x);

        }

    }

}

bool vis[];

void bfs(int s){

    memset(vis,,sizeof(vis));

    queue<int>q;

    q.push(s);vis[s]=true;bfn[]=++_bfn;

    while(!q.empty()){

        int c=q.front();q.pop();

        for(int i=last[c];i;i=e[i].next){

            if(!vis[e[i].to]){

                q.push(e[i].to);

                vis[e[i].to]=true;

                bfn[e[i].to]=++_bfn;

            }

        }

    }

}

void yuchuli(){

    dfs();

    bfs();

    memset(lf,,sizeof(lf));

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

        for(int j=;j<=;j++){

            int anc=f[i][j];

            if(!anc)break;

            gmin(lf[anc][j],bfn[i]);

            gmax(rf[anc][j],bfn[i]);

        }

    }

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

        lf[i][]=rf[i][]=bfn[i];

}

namespace bit{

    ll a1[],a2[];

    ll qzh(int r){

        ll s1=,s2=;

        for(int i=r;i>=;i-=i&-i) s1+=a1[i], s2+=a2[i];

        return (r+)*s1-s2;

    }

    ll sum(int l,int r){

        return qzh(r)-qzh(l-);

    }

    void edt(ll a,ll s1){

        ll s2=a*s1;

        for(;a<=n;a+=a&-a) a1[a]+=s1, a2[a]+=s2;

    }

    void edt(int l,int r,ll a) {edt(l,a); edt(r+,-a);}

}

void _chg(int x,int y){

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

        if(!rf[x][i])break;

        bit::edt(lf[x][i],rf[x][i],y);

    }

}

ll _qry(int x){

    sum=;

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

        if(!rf[x][i])break;

        sum=sum+bit::sum(lf[x][i],rf[x][i]);

    }

    return sum;

}

int main(){

    //FO(tree2);

    n=gi;m=gi;

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

        int a,b;

        a=gi;b=gi;

        link(a,b);

    }

    yuchuli();

    while(m--){

        int op,x,y;

        op=gi;

        if(op==){

            x=gi;

            printf("%I64d\n",_qry(x));

        }

        if(op==){

            x=gi;y=gi;

            _chg(x,y);

            //puts("");

        }

    }

}