题目连接

关于点分树的一些地方今天终于弄明白了，这个题理解的还可以，就是有点卡常，调了好久还是跑的很慢。。。。。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
using namespace std;

char buffer[100001],*S,*T;
inline char Get_Char()
{
    if (S==T)
    {
        T=(S=buffer)+fread(buffer,1,100001,stdin);
        if (S==T) return EOF;
    }
    return *S++;
}
inline int read()
{
    char c;int re=0;
    for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
    while(c>='0'&&c<='9') re=re*10+(c-'0'),c=Get_Char();
    return re;
}


const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const double eps=1e-8;
const int maxn=100100;
int n,m;

int head[maxn],ver[maxn<<1],nt[maxn<<1],tot=1;
int a[maxn];
void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}


int d[maxn],id[maxn],rk[maxn<<1],dd[maxn<<1];
int f[maxn<<1][20],_log[maxn<<1];
int tcnt=0;

void dfs(int x,int fa)
{
    id[x]=++tcnt;rk[tcnt]=x;dd[tcnt]=d[x];
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y==fa) continue;
        d[y]=d[x]+1;
        dfs(y,x);
        rk[++tcnt]=x,dd[tcnt]=d[x];
    }
}

void ST(void)
{
    _log[0]=-1;
    for(int i=1;i<=tcnt;i++)
    {
        f[i][0]=i;
        _log[i]=(i&(i-1))==0?_log[i-1]+1:_log[i-1];
    }

    int t=_log[tcnt]+1;
    for(int j=1;j<=t;j++)
    {
        for(int i=1;i<=tcnt-(1<<j)+1;i++)
            f[i][j]=dd[f[i][j-1]]<dd[f[i+(1<<(j-1))][j-1]]?f[i][j-1]:f[i+(1<<(j-1))][j-1];

    }
}

int lca(int x,int y)
{
    if(id[x]>id[y]) swap(x,y);
    x=id[x],y=id[y];
    int k=_log[y-x+1];
    return dd[f[x][k]]<dd[f[y-(1<<k)+1][k]]?rk[f[x][k]]:rk[f[y-(1<<k)+1][k]];
}

int dis(int x,int y)
{
    return d[x]+d[y]-2*d[lca(x,y)];
}




int maxpart[maxn],si[maxn],fa[maxn],sit[maxn];
bool ha[maxn];
int root,maxsi;
void dfs_size(int x,int fa)
{
    si[x]=1,maxpart[x]=0;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y==fa||ha[y]) continue;
        dfs_size(y,x);
        si[x]+=si[y];
        maxpart[x]=max(maxpart[x],si[y]);
    }
}
void dfs_root(int nowroot,int x,int fa)
{
    maxpart[x]=max(maxpart[x],si[nowroot]-si[x]);
    if(maxsi>maxpart[x])
    {
        maxsi=maxpart[x];
        root=x;
    }
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y==fa||ha[y]) continue;
        dfs_root(nowroot,y,x);
    }
}

void dfs_for_tree(int x,int f)
{
    maxsi=inf;
    dfs_size(x,0);
    dfs_root(x,x,0);

    int rt=root;
    sit[rt]=si[x];
    ha[rt]=true;
    fa[rt]=f;

    for(int i=head[rt];i;i=nt[i])
    {
        int y=ver[i];
        if(ha[y]) continue;
        dfs_for_tree(y,rt);
    }
}



int cnt=0;
int rt1[maxn],rt2[maxn];

struct node
{
    int lc,rc;
    int sum;
}t[maxn<<7];

int newnode(void)
{
    cnt++;
    t[cnt].lc=t[cnt].rc=t[cnt].sum=0;
    return cnt;
}
void change(int &p,int l,int r,int pos,int val)
{
    if(!p) p=newnode();
    t[p].sum+=val;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(pos<=mid) change(t[p].lc,l,mid,pos,val);
    else change(t[p].rc,mid+1,r,pos,val);
}

int ask(int p,int l,int r,int askl,int askr)
{
    if(!p||askl>askr) return 0;
    if(askl<=l&&r<=askr) return t[p].sum;

    int ans=0;
    int mid=(l+r)>>1;
    if(askl<=mid) ans+=ask(t[p].lc,l,mid,askl,askr);
    if(askr>=mid+1) ans+=ask(t[p].rc,mid+1,r,askl,askr);
    return ans;
}



void change(int x,int val)
{
    int now=x;
    while(now)
    {
        change(rt1[now],0,sit[now],dis(now,x),val);
        if(fa[now]) change(rt2[now],0,sit[now],dis(fa[now],x),val);
        now=fa[now];
    }
}

int ask(int x,int k)
{
    int ans=0,now=x,last=0;
    while(now)
    {
        int d=dis(now,x);
        ans+=ask(rt1[now],0,sit[now],0,k-d);
        ans-=ask(rt2[last],0,sit[last],0,k-d);
        last=now;
        now=fa[now];
    }
    return ans;
}

void init(void)
{
    d[0]=-1;
    dfs(1,0);
    ST();

    dfs_for_tree(1,0);

    for(int i=1;i<=n;i++)
        change(i,a[i]);
}

int main(void)
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    int x,y;
    for(int i=1;i<n;i++)
    {
        x=read(),y=read();
        add(x,y);
        add(y,x);
    }
    init();
    int last=0,op;
    for(int i=1;i<=m;i++)
    {
        op=read(),x=read(),y=read();
        x^=last,y^=last;
        if(op==0)
            printf("%d\n",last=ask(x,y));
        else change(x,y-a[x]),a[x]=y;
    }
    return 0;
}