(其实模板题没必要在这里水题解的……主要是想说这个qwq)
小常数的快乐.jpg
我也不知道我为啥常数特别小跑得飞快……不加快读就能在 luogu 的最优解上跑到 rank5 (
说不定深夜提交个 fread 版本能上rk3
给定一棵带点权的树,边权为1,在线处理m次操作
首先建点分树。对于每个点维护两个树状数组,以距离为下标,权值为内容。第一个维护子树中距离该点为k的权值和,第二个维护父亲的内容(同第一个)。
对于修改操作,暴力爬树高,\(log^2\) 复杂度(树高加上树状数组)。
对于查询操作,一样爬树高,进行容斥(把当前子树 \(k\) 的先加起来,往祖先上爬,如果距离小于 \(k\) ,假设为 \(d\),到祖先上去求一个 \(k-d\),再容斥掉原来这棵子树里被计算过的)。
顺便,把最开始的建树当成 modify 能省很多事qwq
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int N=1e5+10,inf=1e9+7;
struct edge
{
int to,nxt;
}e[N<<1];
int n,m,head[N],val[N],fa[N][20],dis[N][20],sz[N],f[N],dep[N],rt,siz,tot=0;
bool vis[N];
vector<int> sbit[N],fbit[N];
void add( int u,int v )
{
e[++tot]=(edge){v,head[u]}; head[u]=tot;
e[++tot]=(edge){u,head[v]}; head[v]=tot;
}
void get_rt( int x,int fat )
{
sz[x]=1; f[x]=0;
for ( int i=head[x]; i; i=e[i].nxt )
{
int y=e[i].to;
if ( vis[y] || fat==y ) continue;
get_rt( y,x ); sz[x]+=sz[y]; f[x]=max( f[x],sz[y] );
}
f[x]=max( f[x],siz-sz[x] );
if ( f[x]<f[rt] ) rt=x;
}
void pre_build( int x,int ancestor,int fat,int d )
{
for ( int i=head[x]; i; i=e[i].nxt )
{
int y=e[i].to;
if ( vis[y] || y==fat ) continue;
fa[y][++dep[y]]=ancestor; dis[y][dep[y]]=d;
pre_build( y,ancestor,x,d+1 );
}
}
void build( int x )
{
vis[x]=1; pre_build( x,x,0,1 );
int sav=siz; sbit[x].resize( siz+1 ); fbit[x].resize( siz+1 );
for ( int i=head[x]; i; i=e[i].nxt )
{
int y=e[i].to; if ( vis[y] ) continue;
siz=sz[y]; if ( siz>sz[x] ) siz=sav-sz[x];
rt=0; get_rt( y,x ); build( rt );
}
}
int qsum_s( int x,int k )
{
int res=val[x],lim=sbit[x].size()-1; k=min( k,lim );
for ( int i=k; i; i-=lowbit(i) ) res+=sbit[x][i];
return res;
}
int qsum_f( int x,int k )
{
int res=0,lim=fbit[x].size()-1; k=min( k,lim );
for ( int i=k; i; i-=lowbit(i) ) res+=fbit[x][i];
return res;
}
void modify( int x,int v )
{
int d=dis[x][dep[x]],lim=sbit[x].size()-1;
for ( int j=d; j<=lim && j; j+=lowbit(j) ) fbit[x][j]+=v;
for ( int i=dep[x]; i; i-- )
{
d=dis[x][i]; lim=sbit[fa[x][i]].size()-1;
for ( int j=d; j<=lim; j+=lowbit(j) ) sbit[fa[x][i]][j]+=v;
d=dis[x][i-1];
for ( int j=d; j<=lim && j; j+=lowbit(j) ) fbit[fa[x][i]][j]+=v;
}
}
int query( int x,int k )
{
int res=qsum_s( x,k );
for ( int i=dep[x]; i; i-- )
if ( dis[x][i]<=k ) res+=qsum_s( fa[x][i],k-dis[x][i] )-qsum_f( fa[x][i+1],k-dis[x][i] );
return res;
}
int main()
{
scanf( "%d%d",&n,&m );
for ( int i=1; i<=n; i++ )
scanf( "%d",&val[i] );
for ( int i=1,u,v; i<n; i++ )
scanf( "%d%d",&u,&v ),add( u,v );
f[0]=inf; siz=n; get_rt( 1,0 ); build( rt );
for ( int i=1; i<=n; i++ )
fa[i][dep[i]+1]=i;
for ( int i=1; i<=n; i++ )
modify( i,val[i] );
int las=0;
while ( m-- )
{
int opt,x,y; scanf( "%d%d%d",&opt,&x,&y );
x^=las; y^=las;
if ( opt==0 ) las=query( x,y ),printf( "%d\n",las );
else modify( x,y-val[x] ),val[x]=y;
}
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章