题解 P3178 【[HAOI2015]树上操作】
NOIP前一天还来水题解
竟然有一样脑回路新奇的题解。。只是不太明白为啥要用线段树维护Fenwicktree吼啊
首先把这个树的euler tour跑出来。首先考虑单点修改：
我们知道在欧拉序上一个点刚刚被访问要记录一次，离开会记录一次，于是我们在刚刚访问的位置+c，离开位置-c；
对于一个路径查询，我们需要计算一下1-这个点的前缀和，可以考虑树状数组。查询是进入还是离开的点呢？实际上都一样，因为进入离开之间所有点必定是两两配对的，所以算出来肯定是0.
考虑子树修改稍显麻烦，在一个点用一个树状数组记录+(dep[x]-1)*c（进入时加离开时减），
同时用一个等同于单点修改的记录一下+c，
当我们查询时，考虑所有加子树的贡献，就是
（u查询点）sum1是+c,sum0是+c*(dep[x-1])
然后考虑完所有单点加和子树加的贡献，就仅仅需要再计算一下初始到根的权值和就好。
代码非常简洁QWQ1.6k速度碾压树剖（实际上在此之前也写过一个树剖）
/*Heroes Never Die!*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define MAXN 100006
struct edge{
ll u;edge* next;
edge( ll u = 0 , edge* next = NULL ):u(u),next(next) {}
void insert( ll u ) {
if( this->next == NULL ) this->next = new edge(u,NULL);
else this->next = new edge( u,this->next );
}
}e[MAXN];
ll in[MAXN],out[MAXN] , n , N , m , sdep[MAXN] , w[MAXN] , dep[MAXN];
ll S[3][MAXN<<1];//0 : 单点更值 ， 1 值*dep 2 个数
void add( ll x , ll c , ll p ) { while( x <= N ) S[p][x] += c , x += x&-x; }
ll sum( ll x , ll p ) { ll res = 0; while( x > 0 ) res += S[p][x], x -= x & -x; return res; }
void addpoint( ll x ,ll c ) {
add( in[x] , c , 0 ) , add( out[x] , -c , 0 );
}
void add_sub( ll x , ll c ) {
add( in[x] , c*(dep[x]-1) , 1 ) , add( out[x] , -c*(dep[x]-1) , 1 ),
add( in[x] , c , 2 ) , add( out[x] , -c , 2 );
}
ll query( ll x ) {
return sdep[x] + sum(in[x],0) + dep[x] * sum( in[x],2 ) - sum(in[x],1);
}
void dfs( ll u , ll fa ) {
in[u] = ++N;
for( edge* n = e[u].next;n!=NULL;n=n->next ) {
ll v = n->u;
if( v == fa ) continue;
sdep[v] = w[v] + sdep[u] , dep[v] = dep[u] + 1;
dfs(v , u);
}
out[u] = ++N;
}
int main() {
freopen("input","r",stdin);
freopen("o","w",stdout);
cin >> n >> m;
for( ll i = 1 ; i <= n ; ++ i ) scanf("%lld",&w[i]);
for( ll i = 0 ,u,v ; i < n - 1 ; ++ i )
scanf("%lld%lld",&u,&v),e[u].insert(v),e[v].insert(u);
sdep[1] = w[1] , dep[1] = 1;
dfs( 1 , 1 );
for( ll i = 0,opt,u,v ; i < m ; ++ i ){
scanf("%lld%lld",&opt,&u);
if( opt == 1 ) scanf("%lld",&v) , addpoint(u,v);
else if( opt == 2 ) scanf("%lld",&v) , add_sub(u,v);
else printf("%lld\n",query(u));
}
}
//qwq考虑树剖的话，如果不抄板子我们知道只需要统计到根。。所以查询一个while就够了，具体看代码：
/*Heroes Never Die!*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
typedef long long ll;
using namespace std;
#define MAXN 100006
struct edge{
ll u;edge* next;
edge(ll u=0,edge* next=NULL):u(u),next(next) {}
void insert( ll u ) {
if(this->next == NULL) this->next = new edge(u,NULL);
else this->next = new edge(u,this->next);
}
}e[MAXN];
ll siz[MAXN] , hea[MAXN] , pre[MAXN] , top[MAXN] , tig[MAXN] , bac[MAXN] , dep[MAXN],cnt;
ll w[MAXN] ;
ll n , m;
void dfs(ll u,ll fa) {
siz[u] = 1;
for( edge* n = e[u].next;n!=NULL;n=n->next ) {
ll v = n->u;
if(v == fa) continue;
dep[v] = dep[u] + 1 , pre[v] = u;
dfs(v,u);
siz[u] += siz[v];
if(!hea[u]||siz[hea[u]] < siz[v]) hea[u] = v;
}
}
void dfs2(ll u,ll to) {
tig[u] = ++cnt , bac[cnt] = u , top[u] = to;
if( !hea[u] )return;
dfs2(hea[u] , to);
for( edge* n = e[u].next;n!=NULL;n=n->next ) {
ll v = n->u;
if( v == pre[u] || v == hea[u] ) continue;
dfs2(v,v);
}
}
ll S[MAXN<<2] , lazy[MAXN<<2];
void pushup( ll rt ) {
S[rt] = S[rt<<1] + S[rt<<1|1];
}
void pushdown( ll rt , ll m ) {
if( lazy[rt] ) {
S[rt<<1] += lazy[rt] * ( m - (m>>1) ),
S[rt<<1|1] += lazy[rt] * ( m >> 1 ),
lazy[rt<<1] += lazy[rt] ,
lazy[rt<<1|1] += lazy[rt],
lazy[rt] = 0;
}
}
void build( ll rt ,ll l ,ll r ) {
if( l == r ) { S[rt] = w[bac[l]] ; return; }
ll m = l + r >> 1;
build(rt<<1 , l , m);
build(rt<<1|1 , m+1 , r);
pushup( rt );
}
void update(ll rt,ll l,ll r,ll L,ll R,ll c){
if( L <= l && R >= r ) { S[rt] += c*(r-l+1) , lazy[rt] += c; return; }
ll m = l + r >> 1;
pushdown(rt , r - l + 1);
if( L <= m ) update( rt<<1 , l , m, L ,R, c );
if( R > m ) update( rt<<1|1, m+1 , r , L , R , c );
pushup(rt);
}
ll query( ll rt, ll l,ll r,ll L,ll R ) {
if( L <= l && R >= r ) return S[rt];
pushdown(rt , r - l + 1);
ll m = l + r >> 1, res = 0;
if( L <= m ) res += query( rt<<1 , l , m , L , R );
if( R > m ) res += query( rt<<1|1 , m + 1, r , L, R );
return res;
}
ll up( ll u ){
ll res = 0;
while( u ) {
res += query( 1 , 1 , n , tig[top[u]] , tig[u] );
u = pre[top[u]];
}
return res;
}
void add_point( ll u , ll c ) {
update( 1 , 1 , n , tig[u] , tig[u] , c );
}
void add_sub( ll u , ll c ) {
update( 1 , 1 , n , tig[u] , tig[u] + siz[u] - 1 , c );
}
int main() {
// freopen("input","r",stdin);
// freopen("o","w",stdout);
cin >> n >> m;
ll res = 0;
for( ll i = 1 ; i <= n ; ++ i ) scanf("%lld",&w[i]),res += w[i];
for( ll i = 0,u,v ; i < n-1 ; ++ i )
scanf("%lld%lld",&u,&v) , e[u].insert(v), e[v].insert(u);
dfs(1,1) , dfs2(1,1);
build(1,1,n);
for( ll i = 0,u,v,op ; i < m ; ++ i ) {
scanf("%lld",&op);
if( op == 1 ) scanf("%lld%lld",&u,&v),add_point(u,v);
else if( op == 2 ) scanf("%lld%lld",&u,&v) , add_sub( u , v );
else scanf("%lld",&u) , printf("%lld\n",up(u));
}
}