這是一道動態點分治好題。
在點分樹上，對于每個點，維護兩個樹狀數組，一個維護離點分中心距離不超過某個值的點權和，另一個維護離點分中心的父親距離不超過某個值的點權和。注意樹狀數組的大小不必開到聯通子樹的大小，而是離某個定點的距離最大值就行了。
最后bzoj上好像是rk11？看來跑得還挺快的。
#include<cstdio>
#include<utility>
#include<vector>
#include<cstring>
#include<cctype>
using namespace std;
const int N=
200005;
inline char read() {
static const int IN_LEN =
1000000;
static char buf[IN_LEN], *s, *t;
if (s == t) {t = (s = buf) + fread(buf,
1, IN_LEN, stdin);
if (s == t)
return -
1;}
return *s++;
}
template<
class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig =
false, c = read(); !
isdigit(c); c = read()) {
if (c ==
'-') iosig =
true;
if (c == -
1)
return;}
for (x =
0;
isdigit(c); c = read())x = (x + (x <<
2) <<
1) + (c ^
'0');
if (iosig) x = -x;
}
const int OUT_LEN =
10000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(
char c) {
if (oh == obuf + OUT_LEN) fwrite(obuf,
1, OUT_LEN, stdout), oh = obuf;*oh++ = c;
}
template<
class T>
inline void print(T x) {
static int buf[
30], cnt;
if (x ==
0) {print(
'0');}
else {
if (x <
0) print(
'-'), x = -x;
for (cnt =
0; x; x /=
10) buf[++cnt] = x %
10 +
48;
while (cnt) print((
char)buf[cnt--]);}
}
inline void flush() {fwrite(obuf,
1, oh - obuf, stdout);
}
struct BIT{
int*a,n;
inline void init(){a=
new int[n];
memset(a,
0,n<<
2);--a;}
inline void add(
int x,
int v){++x;
for(
register int i=x;i<=n;i+=i&-i)a[i]+=v;}
inline int query(
int x){++x;
register int s=
0,i=x;
for(;i;i^=i&-i)s+=a[i];
return s;}
};
inline void up(
int&a,
int b){
if(a<b)a=b;}
inline int min(
int a,
int b){
return a>b?b:a;}
int n,m,i,v[N],x,y,o,la;
template<
class T>
struct vec{T *a;
int n;
void clear(){
if(n>
0)
delete[]a,a=
0,n=
0;}
void push_back(
const T&x){
if((n&-n)==n){T*_a=
new T[n*
2+
1];
memcpy(_a,a,n*
sizeof(T));
delete[]a;a=_a;}a[n++]=x;}T&
operator[](
const int&x){
return a[x];}
inline int size(){
return n;}
};
struct tree{
struct edge{
int to,next;}e[N<<
1];
int h[N],xb,f[N],sz[N],sum,rt;
bool b[N];vec<pair<
int,
int> > d[N];BIT a[N],c[N];
inline void addedge(
int u,
int v){e[++xb]=(edge){v,h[u]},h[u]=xb;e[++xb]=(edge){u,h[v]},h[v]=xb;}
void dfs(
int x,
int fa){sz[x]=f[x]=
1;
for(
int i=h[x];i;i=e[i].next)
if(e[i].to!=fa && !b[e[i].to])dfs(e[i].to,x),sz[x]+=sz[e[i].to],up(f[x],sz[e[i].to]);up(f[x],sum-sz[x]);
if(f[x]<f[rt])rt=x;}
void getdis(
int x,
int f,
int dd){d[x].push_back(make_pair(dd,rt));
for(
int i=h[x];i;i=e[i].next)
if(e[i].to!=f && !b[e[i].to])getdis(e[i].to,x,dd+
1);}
inline void work(
int x){b[x]=
1;getdis(x,
0,
0);
int ts=sum;
for(
int i=h[x];i;i=e[i].next)
if(!b[e[i].to])sum=sz[e[i].to]>sz[x]?ts-sz[x]:sz[e[i].to],dfs(e[i].to,rt=
0),work(rt);}
inline void add(
int x,
int y){
register int i;
for(i=d[x].size()-
1;i>=
0;--i)a[d[x][i].second].add(d[x][i].first,y);
for(i=d[x].size()-
1;i;--i)c[d[x][i].second].add(d[x][i-
1].first,y);}
inline void fix(
int x){
register int i;
for(i=d[x].size()-
1;i>=
0;--i)up(a[d[x][i].second].n,
1+d[x][i].first);
for(i=d[x].size()-
1;i;--i)up(c[d[x][i].second].n,
1+d[x][i-
1].first);}
inline int query(
int x,
int y){
register int i=d[x].size()-
1,ans=a[x].query(min(y,a[x].n-
1)),p,q;
for(;i;--i){p=d[x][i].second,q=d[x][i-
1].second;
if(y>=d[x][i-
1].first){ans+=a[q].query(min(y-d[x][i-
1].first,a[q].n-
1));ans-=c[p].query(min(y-d[x][i-
1].first,c[p].n-
1));}}
return ans;}
inline void prepare(){sum=n,*f=
1<<
30,dfs(
1,
0);work(rt);
register int i=
1;
for(;i<=n;++i)fix(i);
for(i=
1;i<=n;++i)a[i].init(),c[i].init();
for(i=
1;i<=n;++i)add(i,v[i]);}
}t;
int main(){read(n),read(m);
for(i=
1;i<=n;++i)read(v[i]);
for(i=
1;i<n;++i)read(x),read(y),t.addedge(x,y);t.prepare();
while(m--){read(o),read(x),read(y);x^=la,y^=la;
if(o)t.add(x,y-v[x]),v[x]=y;
else print(la=t.query(x,y)),print(
'\n');}
return flush(),
0;
}
總結
以上是生活随笔為你收集整理的bzoj3730震波的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
