题解 P3676 【小清新数据结构题】
Kelin
2018-02-18 20:10:22
题意:求当u为根时,所有子树的点权和的平方和,带修改
考虑没有换根的操作(假设当前根是$1$)如何计算所求
考虑到修改一个点u的权值,只会影响到$path(1,u)$上的点的子树点权和
记$s_i$为$i$子树的点权和,把修改变成增加,那么其贡献就是
$\sum_{i\in path(1,u)}(s_i+a)^2-\sum_{i\in path(1,u)}s_i^2=a^2len+2a\sum_{i\in path(1,u)}s_i$
所以只要$dfs$预处理出$ans=\sum_{i=1}^ns_i^2$然后维护$\sum_{i\in path(1,u)}s_i$就$ok$了
注意修改完还要$ans+=a^2len+2a\sum_{i\in path(1,u)}s_i$
考虑有换根的操作怎么办?
其实子树点权和受到影响的还是path(1,u)上的点
设$path(1,u)$上的点为$v_1,v_2,\ldots,v_k$(连续的)
对应每个点$v_i$的子树点权和是$a_i$(以$1$为根)和$b_i$(以$u$为根)
注意到$a_{i+1}+b_i=a_1=b_k$($ans_u$表示当根是$u$时的答案)
$ans_u=ans_1-\sum_{i=1}^ka_i^2+\sum_{i=1}^kb_i^2$
$=ans_1-\sum_{i=1}^ka_i^2+\sum_{i=1}^{k-1}(a_1-a_{i+1})^2+b_k^2$
$=ans_1-\sum_{i=2}^ka_i^2+\sum_{i=2}^{k}(a_1-a_i)^2$
$=ans_1+(k-1)a_1^2-2a_1\sum_{i=2}^ka_i$
$=ans+s_1[(k-1)s_1-2(\sum_{i\in path(1,u)}^ks_i-s_1)]$
$=ans+s_1[(k+1)s_1-2\sum_{i\in path(1,u)}^ks_i]$
树上路径点权和显然可以用树剖或者LCT维护
树剖的话没必要写线段树,树状数组就好了
树剖+BIT
```
#include<bits/stdc++.h>
#define fp(i,a,b) for(int i=a,I=b;i<=I;++i)
#define fd(i,a,b) for(int i=a,I=b;i>=I;--i)
#define go(i,u) for(int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
using namespace std;
const int N=2e5+5;
typedef int arr[N];
typedef long long ll;
struct eg{int nx,to;}e[N<<1];
int n,m,ce,cnt;arr w,c,fi,fa,sz,id,pos,dep,son,top;ll ans,c1[N],c2[N];
void dfs(int u){
dep[u]=dep[fa[u]]+(sz[u]=1);
go(i,u)if(v^fa[u]){
fa[v]=u,dfs(v),w[u]+=w[v],sz[u]+=sz[v];
if(sz[v]>sz[son[u]])son[u]=v;
}ans+=1ll*w[u]*w[u];
}
inline void Mdy(int x,ll w){for(int i=x;i<=n;i+=i&(-i))c1[i]+=w,c2[i]+=(ll)x*w;}
inline ll Qry(int x){ll w=0;for(int i=x;i;i-=i&(-i))w+=1ll*(x+1)*c1[i]-c2[i];return w;}
void dfs(int u,int t){
top[u]=t;pos[id[u]=++cnt]=u;
Mdy(id[u],w[u]-w[pos[cnt-1]]);
if(son[u])dfs(son[u],t);
go(i,u)if(v^fa[u]&&v^son[u])dfs(v,v);
}
inline ll qry(int u){
int k=0,x=Qry(1);ll s=0;
for(;u;u=fa[top[u]])
k+=id[u]-id[top[u]]+1,
s+=Qry(id[u])-Qry(id[top[u]]-1);
return ans+x*((k+1)*x-(s<<1));
}
inline void mdy(int u,int x){
int k=0;ll s=0;
for(;u;u=fa[top[u]])
k+=id[u]-id[top[u]]+1,
s+=Qry(id[u])-Qry(id[top[u]]-1),
Mdy(id[top[u]],x),Mdy(id[u]+1,-x);
ans+=x*(x*k+(s<<1));
}
inline void add(int u,int v){e[++ce]=eg{fi[u],v};fi[u]=ce;}
int main(){
scanf("%d%d",&n,&m);int u,v,o;
fp(i,2,n)scanf("%d%d",&u,&v),add(u,v),add(v,u);
fp(i,1,n)scanf("%d",c+i),w[i]=c[i];dfs(1);dfs(1,1);
while(m--)
scanf("%d%d",&o,&u),
o==1?scanf("%d",&v),v-=c[u],c[u]+=v,mdy(u,v):(void)printf("%lld\n",qry(u));
return 0;
}
```
LCT
```
#include<bits/stdc++.h>
#define fp(i,a,b) for(int i=a,I=b;i<=I;++i)
#define fd(i,a,b) for(int i=a,I=b;i>=I;--i)
#define go(i,u) for(int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
using namespace std;
const int N=2e5+5;
typedef int arr[N];
typedef long long ll;
struct eg{int nx,to;}e[N<<1];
int n,m,ce;arr w,c,fi;ll ans;
int top,ch[N][2];arr S,rev,sz,fa,tg;ll s[N];
#define lc(u)(ch[u][0])
#define rc(u)(ch[u][1])
inline void down(int p){
if(rev[p]){
rev[lc(p)]^=1,rev[rc(p)]^=1;
swap(lc(p),rc(p)),rev[p]=0;
}w[p]+=tg[p];
fp(i,0,1){
int k=ch[p][i];
tg[k]+=tg[p];
s[k]+=tg[p]*sz[k];
}tg[p]=0;
}
inline void up(int p){
s[p]=w[p]+s[lc(p)]+s[rc(p)];
sz[p]=sz[lc(p)]+sz[rc(p)]+1;
}
inline bool gf(int u){return rc(fa[u])==u;}
inline bool ir(int u){return lc(fa[u])!=u&&rc(fa[u])!=u;}
inline void rot(int u){
int p=fa[u],k=gf(u);
if(!ir(p))ch[fa[p]][gf(p)]=u;
if(ch[u][!k])fa[ch[u][!k]]=p;
ch[p][k]=ch[u][!k],ch[u][!k]=p;
fa[u]=fa[p],fa[p]=u,up(p);
}
void splay(int u){
S[top=1]=u;
for(int i=u;!ir(i);i=fa[i])S[++top]=fa[i];
fd(i,top,1)down(S[i]);
for(int f=fa[u];!ir(u);rot(u),f=fa[u])
if(!ir(f))rot(gf(u)==gf(f)?f:u);
up(u);
}
inline void acc(int u){for(int v=0;u;u=fa[v=u])splay(u),ch[u][1]=v,up(u);}
inline void mkrt(int u){acc(u),splay(u),rev[u]=1;}
inline void close(int u,int v){mkrt(u),acc(v),splay(v);}
inline void link(int u,int v){mkrt(u),fa[u]=v;}
void dfs(int u){go(i,u)if(v^fa[u])fa[v]=u,dfs(v),w[u]+=w[v];ans+=1ll*w[u]*w[u];}
inline ll qry(int u){return close(u,1),ans+w[1]*(1ll*(sz[1]+1)*w[1]-(s[1]<<1));}
inline void mdy(int u,int x){close(u,1),ans+=x*(x*sz[1]+(s[1]<<1)),tg[1]+=x,s[1]+=sz[1]*x;}
inline void add(int u,int v){e[++ce]=eg{fi[u],v};fi[u]=ce;}
int main(){
scanf("%d%d",&n,&m);int u,v,o;
fp(i,2,n)scanf("%d%d",&u,&v),add(u,v),add(v,u);
fp(i,1,n)scanf("%d",c+i),w[i]=c[i];dfs(1);
while(m--)
scanf("%d%d",&o,&u),
o==1?scanf("%d",&v),v-=c[u],c[u]+=v,mdy(u,v):(void)printf("%lld\n",qry(u));
return 0;
}
```
虽说树剖复杂度是$O(n\log^2n)$,$LCT$复杂度是$O(n\log n)$,但是我不得不感叹$LCT$常数真大