【學習筆記】點分治
一、概念
有一些題要求我們統計某些點對的數量，限制一般和點間的路徑有關，\(O(n^2)\) 的時間復雜度無法承受。我們考慮首先選定一個根，此時路徑分為兩類：
- 經過根
- 不經過根
其中不經過根的可以在刪掉根后在每個子樹中進行統計，遞歸求解。于是只用處理經過根的情況。那么可以將這條路徑拆成從一個點到根和從根到另一個點，方便地解決。于是只要遞歸層數合理即可獲得一個相當優秀的時間復雜度。可以證明，只要每次選擇的都是當前樹的重心，遞歸層數就是 \(O(\log n)\) 的。
二、例題
1.[bzoj1468]Tree
考慮在當前樹中處理出每個點到根的距離。將所有點的距離排序，有一個 \(l\) 指針和 \(r\) 指針分別指向序列的兩端。可以發現當 \(l\) 和 \(r\) 對應的距離之和滿足要求，\([l+1,r-1]\) 中的點就都能滿足要求。于是就累加答案，在移動 \(l\) 指針即可。否則就向左移動 \(r\) 指針。
可以發現這樣同一個子樹內會統計到不合法的答案，那就在每個子樹內減掉即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=4e4+5,inf=0x3f3f3f3f;
int n,m,enm=1,hd[maxn];
struct{
int v,w,nxt;
}e[maxn<<1];
il void addedge(int u,int v,int w){
e[++enm].v=v;
e[enm].w=w;
e[enm].nxt=hd[u];
hd[u]=enm;
}
vector<int> dv;
int sz[maxn],mxs[maxn],dis[maxn];
bool ban[maxn<<1];
il void dfs1(int u,int fa){
sz[u]=1,mxs[u]=0;
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(ban[i]||v==fa){
continue;
}
dfs1(v,u);
sz[u]+=sz[v];
mxs[u]=max(mxs[u],sz[v]);
}
mxs[u]=max(mxs[u],(int)dv.size()-sz[u]);
}
il void dfs2(int u,int fa){
for(int i=hd[u],v,w;i;i=e[i].nxt){
v=e[i].v,w=e[i].w;
if(ban[i]||v==fa){
continue;
}
dis[v]=dis[u]+w;
dfs2(v,u);
}
}
il int calc(){
int res=0;
int l=0,r=dv.size()-1;
sort(dv.begin(),dv.end(),[](const int &x,const int &y){return dis[x]<dis[y];});
while(l<r){
if(dis[dv[l]]+dis[dv[r]]<=m){
res+=r-l;
l++;
}
else{
r--;
}
}
return res;
}
il void dfs3(int u,int fa){
dv.pb(u);
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(ban[i]||v==fa){
continue;
}
dfs3(v,u);
}
}
il int solve(){
if(dv.size()==1){
return 0;
}
dfs1(dv[0],0);
int mmxs=inf,rt=0;
for(int u:dv){
if(mmxs>mxs[u]){
mmxs=mxs[u],rt=u;
}
}
dis[rt]=0;
dfs2(rt,0);
int res=calc();
for(int i=hd[rt];i;i=e[i].nxt){
if(ban[i]){
continue;
}
dv.clear();
dfs3(e[i].v,rt);
res-=calc();
}
for(int i=hd[rt];i;i=e[i].nxt){
if(ban[i]){
continue;
}
ban[i]=ban[i^1]=1;
dv.clear();
dfs3(e[i].v,0);
res+=solve();
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
addedge(u,v,w);
addedge(v,u,w);
}
cin>>m;
for(int i=1;i<=n;i++){
dv.pb(i);
}
cout<<solve();
return 0;
}
}
int main(){return asbt::main();}
2.聰聰可可
存儲當前到根距離對 \(3\) 取模為 \(0,1,2\) 的點數，在每個子樹上先統計答案，再將這個子樹上的點加入。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
#define gcd __gcd
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=4e4+5,inf=0x3f3f3f3f;
int n,enm=1,hd[maxn];
struct{
int v,w,nxt;
}e[maxn];
il void addedge(int u,int v,int w){
e[++enm].v=v;
e[enm].w=w;
e[enm].nxt=hd[u];
hd[u]=enm;
}
vector<int> dv;
int sz[maxn],mxs[maxn],dis[maxn];
bool ban[maxn];
il void dfs1(int u,int fa){
sz[u]=1,mxs[u]=0;
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(ban[i]||v==fa){
continue;
}
dfs1(v,u);
sz[u]+=sz[v];
mxs[u]=max(mxs[u],sz[v]);
}
mxs[u]=max(mxs[u],(int)dv.size()-sz[u]);
}
il void dfs2(int u,int fa){
for(int i=hd[u],v,w;i;i=e[i].nxt){
v=e[i].v,w=e[i].w;
if(ban[i]||v==fa){
continue;
}
dis[v]=dis[u]+w;
dfs2(v,u);
}
}
int ans1,ans2,nm[3];
il void dfs3(int u,int fa){
ans1+=nm[((3-dis[u])%3+3)%3]<<1;
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(ban[i]||v==fa){
continue;
}
dfs3(v,u);
}
}
il void dfs4(int u,int fa){
nm[dis[u]%3]++;
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(ban[i]||v==fa){
continue;
}
dfs4(v,u);
}
}
il void dfs5(int u,int fa){
dv.pb(u);
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(ban[i]||v==fa){
continue;
}
dfs5(v,u);
}
}
il void solve(){
dfs1(dv[0],0);
int rt=0,mmxs=inf;
for(int u:dv){
if(mmxs>mxs[u]){
mmxs=mxs[u],rt=u;
}
}
// cout<<rt<<"\n";
dis[rt]=0;
dfs2(rt,0);
nm[0]=1,nm[1]=nm[2]=0;
ans1++;
for(int i=hd[rt],v;i;i=e[i].nxt){
if(ban[i]){
continue;
}
v=e[i].v;
dfs3(v,rt);
dfs4(v,rt);
}
for(int i=hd[rt];i;i=e[i].nxt){
if(ban[i]){
continue;
}
ban[i]=ban[i^1]=1;
dv.clear();
dfs5(e[i].v,0);
solve();
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
addedge(u,v,w);
addedge(v,u,w);
}
for(int i=1;i<=n;i++){
dv.pb(i);
}
solve();
ans2=n*n;
// cout<<ans1<<"\n";
cout<<ans1/gcd(ans1,ans2)<<"/"<<ans2/gcd(ans1,ans2);
return 0;
}
}
signed main(){return asbt::main();}
3.[bzoj2599][IOI2011]Race
存儲到根的每個距離的最小深度，類似例 \(2\) 的手法去求即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=4e5+5,maxm=1e6+5;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m,enm=1,hd[maxn];
struct{
int v,w,nxt;
}e[maxn];
il void addedge(int u,int v,int w){
e[++enm].v=v;
e[enm].w=w;
e[enm].nxt=hd[u];
hd[u]=enm;
}
vector<int> dv,vp;
int sz[maxn],mxs[maxn];
int dep[maxn],dis[maxn];
int mdis[maxm],ans=inf;
bool ban[maxn];
il void dfs1(int u,int fa){
sz[u]=1,mxs[u]=0;
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(ban[i]||v==fa){
continue;
}
dfs1(v,u);
sz[u]+=sz[v];
mxs[u]=max(mxs[u],sz[v]);
}
mxs[u]=max(mxs[u],(int)dv.size()-sz[u]);
}
il void dfs2(int u,int fa){
for(int i=hd[u],v,w;i;i=e[i].nxt){
v=e[i].v,w=e[i].w;
if(ban[i]||v==fa){
continue;
}
dep[v]=dep[u]+1;
dis[v]=dis[u]+w;
dfs2(v,u);
}
}
template<typename T>il void dfs3(int u,int fa,T x){
x(u);
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(ban[i]||v==fa){
continue;
}
dfs3(v,u,x);
}
}
il void solve(){
dfs1(dv[0],0);
int rt=0,mmxs=inf;
for(int u:dv){
if(mmxs>mxs[u]){
mmxs=mxs[u],rt=u;
}
}
dis[rt]=dep[rt]=0;
dfs2(rt,0);
vp.pb(0);
mdis[0]=0;
for(int i=hd[rt],v;i;i=e[i].nxt){
if(ban[i]){
continue;
}
v=e[i].v;
dfs3(v,rt,[](int x){if(dis[x]<=m) ans=min(ans,mdis[m-dis[x]]+dep[x]);});
dfs3(v,rt,[](int x){if(dis[x]<=m) mdis[dis[x]]=min(mdis[dis[x]],dep[x]),vp.pb(dis[x]);});
}
for(int x:vp){
mdis[x]=inf;
}
vp.clear();
for(int i=hd[rt],v;i;i=e[i].nxt){
if(ban[i]){
continue;
}
v=e[i].v;
ban[i]=ban[i^1]=1;
dv.clear();
dfs3(v,0,[](int x){dv.pb(x);});
solve();
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
u++,v++;
addedge(u,v,w);
addedge(v,u,w);
}
memset(mdis,0x3f,sizeof mdis);
for(int i=1;i<=n;i++){
dv.pb(i);
}
solve();
cout<<(ans>=inf?-1:ans);
return 0;
}
}
signed main(){return asbt::main();}
4.采藥人的路徑
我們將所有 \(0\) 都記為 \(-1\)，那么整條路徑陰陽平衡用點分治就很簡單了。考慮休息點的限制，那其實就是對于 \((u,v)\)，從 \(u\) 或 \(v\) 出發向上走的過程中前綴和存在 \(0\)。因為我們的 dfs 是從上往下的過程，前綴和序列需要區間加。但我們其實不用考慮前綴和序列的順序，只用看其中有沒有 \(0\) 就好了。于是可以用 FHQ-Treap 來維護。對于每個根鏈和，維護前綴和中有 \(0\) 的點的個數和沒有 \(0\) 的點的個數即可。注意特判以根為端點的情況。時間復雜度 \(O(n\log^2n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
int n,enm=1,hd[maxn];
int sz[maxn],mxs[maxn];
int nm1[maxn],nm2[maxn];
int sum[maxn],tot;
ll ans;
bool ban[maxn],zero[maxn];
vector<int> dv;
struct{
int v,w,nxt;
}e[maxn];
il void addedge(int u,int v,int w){
e[++enm].v=v;
e[enm].w=w;
e[enm].nxt=hd[u];
hd[u]=enm;
}
il void dfs1(int u,int fa){
sz[u]=1,mxs[u]=0;
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(ban[i]||v==fa){
continue;
}
dfs1(v,u);
sz[u]+=sz[v];
mxs[u]=max(mxs[u],sz[v]);
}
mxs[u]=max(mxs[u],tot-sz[u]);
}
namespace fhq{
int rt,tot,ls[maxn],rs[maxn];
int zhi[maxn],jan[maxn],tag[maxn];
int ljt[maxn],top,sz[maxn];
il int New(int v){
int p=top?ljt[top--]:++tot;
ls[p]=rs[p]=0,sz[p]=1;
zhi[p]=v,tag[p]=0;
jan[p]=rand();
return p;
}
il void pushup(int id){
sz[id]=sz[ls[id]]+sz[rs[id]]+1;
}
il void pushdown(int id){
if(tag[id]){
tag[ls[id]]+=tag[id];
tag[rs[id]]+=tag[id];
zhi[ls[id]]+=tag[id];
zhi[rs[id]]+=tag[id];
tag[id]=0;
}
}
il int merge(int p,int q){
if(!p||!q){
return p+q;
}
if(jan[p]<jan[q]){
pushdown(p);
rs[p]=merge(rs[p],q);
pushup(p);
return p;
}
pushdown(q);
ls[q]=merge(p,ls[q]);
pushup(q);
return q;
}
il void split(int id,int &p,int &q,int v){
if(!id){
p=q=0;
return ;
}
pushdown(id);
if(zhi[id]<=v){
p=id;
split(rs[id],rs[p],q,v);
}
else{
q=id;
split(ls[id],p,ls[q],v);
}
pushup(id);
}
il void insert(int v){
tag[rt]+=v,zhi[rt]+=v;
int x,y;
split(rt,x,y,v);
rt=merge(merge(x,New(v)),y);
}
il void erase(int v){
int x,y,z;
split(rt,x,y,v-1);
split(y,y,z,v);
ljt[++top]=y;
rt=merge(merge(x,ls[y]),merge(rs[y],z));
tag[rt]-=v,zhi[rt]-=v;
}
}
il void dfs2(int u,int fa){
int x,y,z;
fhq::split(fhq::rt,x,y,-1);
fhq::split(y,y,z,0);
zero[u]=y;
if(!sum[u]&&fhq::sz[y]>1){
ans++;
}
fhq::rt=fhq::merge(fhq::merge(x,y),z);
if(zero[u]){
ans+=nm1[tot-sum[u]];
}
else{
ans+=nm2[tot-sum[u]];
}
for(int i=hd[u],v,w;i;i=e[i].nxt){
v=e[i].v,w=e[i].w;
if(ban[i]||v==fa){
continue;
}
sum[v]=sum[u]+w;
fhq::insert(w);
dfs2(v,u);
fhq::erase(w);
}
}
template<typename T>il void dfs3(int u,int fa,T x){
x(u);
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(ban[i]||v==fa){
continue;
}
dfs3(v,u,x);
}
}
il void solve(){
tot=dv.size();
dfs1(dv[0],0);
int tmp=inf,rt;
for(int u:dv){
if(tmp>mxs[u]){
tmp=mxs[u];
rt=u;
}
}
for(int i=0;i<=tot<<1;i++){
nm1[i]=nm2[i]=0;
}
for(int i=hd[rt],v,w;i;i=e[i].nxt){
if(ban[i]){
continue;
}
v=e[i].v,w=e[i].w;
sum[v]=w;
fhq::insert(w);
dfs2(v,rt);
fhq::erase(w);
dfs3(v,rt,[](int x){nm1[tot+sum[x]]++;if(zero[x]) nm2[tot+sum[x]]++;});
}
for(int i=hd[rt],v;i;i=e[i].nxt){
if(ban[i]){
continue;
}
v=e[i].v;
ban[i]=ban[i^1]=1;
dv.clear();
dfs3(v,0,[](int x){dv.pb(x);});
solve();
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
w=w?1:-1;
addedge(u,v,w);
addedge(v,u,w);
}
for(int i=1;i<=n;i++){
dv.pb(i);
}
solve();
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
5.「BJOI2017」樹的難題
點分治后，對于和根相連的邊顏色為 \(w\) 的路徑，顯然我們需要將之前的路徑分成與根相連的邊為 \(w\) 的路徑和不為 \(w\) 的路徑分別統計答案。那么我們將根連出的點按照邊顏色排序，分別開兩棵平衡樹，每遇到新的顏色就將兩顆平衡樹合到一塊即可。時間復雜度 \(O(n\log^2n)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fir first
#define sec second
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5,inf=1e18;
int n,m,_l,_r,a[maxn],ans=-inf;
int sz[maxn],mxsz[maxn];
int col[maxn],dep[maxn],dis[maxn];
bool ban[maxn];
vector<int> dv;
vector<pii> e[maxn];
il void dfs1(int u,int fa,int tot){
sz[u]=1,mxsz[u]=0;
for(pii i:e[u]){
int v=i.fir;
if(v==fa||ban[v]){
continue;
}
dfs1(v,u,tot);
sz[u]+=sz[v];
mxsz[u]=max(mxsz[u],sz[v]);
}
mxsz[u]=max(mxsz[u],tot-sz[u]);
}
il void dfs2(int u,int fa){
for(pii i:e[u]){
int v=i.fir,w=i.sec;
if(v==fa||ban[v]){
continue;
}
dep[v]=dep[u]+1;
col[v]=w,dis[v]=dis[u];
if(w!=col[u]){
dis[v]+=a[w];
}
dfs2(v,u);
}
}
int RT[2],tot;
int ls[maxn],rs[maxn];
int shn[maxn],jan[maxn];
int zhi[maxn],mxz[maxn];
il int New(int x,int y){
tot++;
ls[tot]=rs[tot]=0;
shn[tot]=x,jan[tot]=rand();
zhi[tot]=mxz[tot]=y;
return tot;
}
il void pushup(int id){
mxz[id]=max({mxz[ls[id]],mxz[rs[id]],zhi[id]});
}
il int merge(int p,int q){
if(!p||!q){
return p+q;
}
if(jan[p]<jan[q]){
rs[p]=merge(rs[p],q);
pushup(p);
return p;
}
ls[q]=merge(p,ls[q]);
pushup(q);
return q;
}
il void split(int id,int x,int &p,int &q){
if(!id){
p=q=0;
return ;
}
if(shn[id]<=x){
p=id;
split(rs[id],x,rs[p],q);
}
else{
q=id;
split(ls[id],x,p,ls[q]);
}
pushup(id);
}
il void insert(int &id,int x,int y){
int p,q;
split(id,x,p,q);
id=merge(merge(p,New(x,y)),q);
}
il int query(int &id,int l,int r){
int x,y,z;
split(id,l-1,x,y);
split(y,r,y,z);
int res=mxz[y];
id=merge(merge(x,y),z);
return res;
}
il void dfs3(int &id){
if(!id){
return ;
}
dfs3(ls[id]),dfs3(rs[id]);
mxz[id]=zhi[id];
int x,y;
split(RT[0],shn[id],x,y);
RT[0]=merge(merge(x,id),y);
id=0;
}
template<typename T>il void dfs4(int u,int fa,T x){
x(u);
for(pii i:e[u]){
int v=i.fir;
if(v==fa||ban[v]){
continue;
}
dfs4(v,u,x);
}
}
il void solve(){
dfs1(dv[0],0,dv.size());
int rt,tmp=inf;
for(int u:dv){
if(tmp>mxsz[u]){
tmp=mxsz[u],rt=u;
}
}
col[rt]=dep[rt]=dis[rt]=0;
dfs2(rt,0);
sort(e[rt].begin(),e[rt].end(),[](pii x,pii y){return x.sec<y.sec;});
RT[0]=RT[1]=0;
mxz[0]=-inf,tot=0;
insert(RT[0],0,0);
for(int i=0,v,w;i<e[rt].size();i++){
v=e[rt][i].fir,w=e[rt][i].sec;
if(i&&w!=e[rt][i-1].sec){
dfs3(RT[1]);
}
if(ban[v]){
continue;
}
dfs4(v,rt,[=](int x){ans=max({ans,dis[x]+query(RT[0],_l-dep[x],_r-dep[x]),dis[x]+query(RT[1],_l-dep[x],_r-dep[x])-a[w]});});
dfs4(v,rt,[](int x){insert(RT[1],dep[x],dis[x]);});
}
ban[rt]=1;
for(pii i:e[rt]){
int v=i.fir,w=i.sec;
if(ban[v]){
continue;
}
dv.clear();
dfs4(v,0,[](int x){dv.pb(x);});
solve();
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>_l>>_r;
for(int i=1;i<=m;i++){
cin>>a[i];
}
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
e[u].pb(mp(v,w));
e[v].pb(mp(u,w));
}
for(int i=1;i<=n;i++){
dv.pb(i);
}
solve();
cout<<ans;
return 0;
}
}
signed main(){return asbt::main();}
三、點分樹
在點分治過程中，對當前子樹的重心與刪去后的每個子樹的重心建立父子關系，這樣可以建成一棵新樹。對這棵樹上的每一個點維護子樹內的信息，就可以動態修改地進行點分治了。
1.[BZOJ3730]點分樹 | 震波(模板)
在點分樹的每一個點上用兩棵平衡樹維護距離與權值的信息（一棵維護到自己的距離，另一棵維護到點分樹上父親的距離）。修改和查詢就只需考察根鏈就好了。
現學了一下替罪羊樹，十分的快。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define ull unsigned ll
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
namespace IO{
const int bufsz=1<<20;
char ibuf[bufsz],*p1=ibuf,*p2=ibuf;
#define getchar() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,bufsz,stdin),p1==p2)?EOF:*p1++)
il int read(){
char ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
int x=0;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
#undef getchar
}
using IO::read;
const int maxn=1e5+5,maxm=4e6+5;
const int inf=0x3f3f3f3f;
int n,m,a[maxn];
vector<int> e[maxn];
namespace LCA{
int cnt,dep[maxn],dfn[maxn];
int idx[maxn<<1],oula[maxn<<1];
il void dfs(int u,int fa){
dep[u]=dep[fa]+1;
dfn[u]=++cnt;
idx[cnt]=u;
oula[cnt]=cnt;
for(int v:e[u]){
if(v==fa){
continue;
}
dfs(v,u);
oula[++cnt]=dfn[u];
}
}
struct{
int st[maxn<<1][22],Log[maxn<<1];
il void build(){
for(int i=2;i<=cnt;i++){
Log[i]=Log[i>>1]+1;
}
for(int i=1;i<=cnt;i++){
st[i][0]=oula[i];
}
for(int j=1;j<=Log[cnt];j++){
for(int i=1;i+(1<<j)-1<=cnt;i++){
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
}
il int query(int l,int r){
int tmp=Log[r-l+1];
return min(st[l][tmp],st[r-(1<<tmp)+1][tmp]);
}
}ST;
il void init(){
dfs(1,0);
ST.build();
}
il int lca(int u,int v){
if(dfn[u]>dfn[v]){
swap(u,v);
}
return idx[ST.query(dfn[u],dfn[v])];
}
il int dis(int u,int v){
return dep[u]+dep[v]-(dep[lca(u,v)]<<1);
}
}
using LCA::dis;
int sz[maxn],mxsz[maxn];
int RT[maxn][2],fa[maxn];
bool ban[maxn];
vector<int> dv;
il void dfs1(int u,int fa,int tot){
sz[u]=1,mxsz[u]=0;
for(int v:e[u]){
if(ban[v]||v==fa){
continue;
}
dfs1(v,u,tot);
sz[u]+=sz[v];
mxsz[u]=max(mxsz[u],sz[v]);
}
mxsz[u]=max(mxsz[u],tot-sz[u]);
}
template<typename T>il void dfs2(int u,int fa,T x){
x(u);
for(int v:e[u]){
if(v==fa||ban[v]){
continue;
}
dfs2(v,u,x);
}
}
namespace gtree{
int tot,ls[maxm],rs[maxm];
int pos[maxm],sz[maxm];
int zhi[maxm],sum[maxm];
int mnl[maxm],mxr[maxm];
int hp[maxm],cnt;
il void pushup(int id){
sz[id]=sz[ls[id]]+sz[rs[id]]+1;
sum[id]=sum[ls[id]]+sum[rs[id]]+zhi[id];
mnl[id]=ls[id]?mnl[ls[id]]:pos[id];
mxr[id]=rs[id]?mxr[rs[id]]:pos[id];
}
il void flatten(int id){
if(!id){
return ;
}
flatten(ls[id]);
hp[++cnt]=id;
flatten(rs[id]);
}
il void build(int &id,int l,int r){
if(l>r){
id=0;
return ;
}
int mid=(l+r)>>1;
id=hp[mid];
build(ls[id],l,mid-1);
build(rs[id],mid+1,r);
pushup(id);
}
il void rebuild(int &id){
if(max(sz[ls[id]],sz[rs[id]])>=sz[id]*0.75){
cnt=0;
flatten(id);
build(id,1,cnt);
}
}
il void insert(int &id,int x,int y){
if(!id){
id=++tot;
sz[id]=1;
mnl[id]=mxr[id]=pos[id]=x;
zhi[id]=sum[id]=y;
return ;
}
if(pos[id]==x){
zhi[id]+=y,sum[id]+=y;
return ;
}
if(x<pos[id]){
insert(ls[id],x,y);
}
else{
insert(rs[id],x,y);
}
pushup(id);
rebuild(id);
}
il int query(int id,int l,int r){
if(!id){
return 0;
}
if(mnl[id]>=l&&mxr[id]<=r){
return sum[id];
}
int res=l<=pos[id]&&r>=pos[id]?zhi[id]:0;
if(l<pos[id]){
res+=query(ls[id],l,r);
}
if(r>pos[id]){
res+=query(rs[id],l,r);
}
return res;
}
}
il int build(){
dfs1(dv[0],0,dv.size());
int rt,tmp=inf;
for(int u:dv){
if(tmp>mxsz[u]){
tmp=mxsz[u],rt=u;
}
}
for(int u:dv){
gtree::insert(RT[rt][0],dis(u,rt),a[u]);
}
ban[rt]=1;
for(int v:e[rt]){
if(ban[v]){
continue;
}
dv.clear();
dfs2(v,0,[](int x){dv.pb(x);});
int nrt=build();
fa[nrt]=rt;
dfs2(v,0,[=](int x){gtree::insert(RT[nrt][1],dis(x,rt),a[x]);});
}
ban[rt]=0;
return rt;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1,u,v;i<n;i++){
u=read(),v=read();
e[u].pb(v),e[v].pb(u);
}
LCA::init();
for(int i=1;i<=n;i++){
dv.pb(i);
}
build();
ll ans=0;
while(m--){
int opt,u,v;
opt=read(),u=read(),v=read();
u^=ans,v^=ans;
if(opt){
int p=u;
while(p){
gtree::insert(RT[p][0],dis(u,p),v-a[u]);
if(fa[p]){
gtree::insert(RT[p][1],dis(u,fa[p]),v-a[u]);
}
p=fa[p];
}
a[u]=v;
}
else{
ans=0;
int p=u;
while(p){
ans+=gtree::query(RT[p][0],0,v-dis(u,p));
if(fa[p]){
ans-=gtree::query(RT[p][1],0,v-dis(u,fa[p]));
}
p=fa[p];
}
printf("%lld\n",ans);
}
}
return 0;
}
}
int main(){return asbt::main();}
2.「ZJOI2015」幻想鄉戰略游戲
考慮一個暴力的貪心：首先將決策點設為 \(1\)，然后每次選擇一個比自己更優的兒子走過去，如果沒有比自己更優的兒子那決策點就是自己。
令 \(u\) 為根，那么 \(u\) 的兒子 \(v\) 比 \(u\) 優當且僅當：
\[(sum_u-sum_v)\times\operatorname{dis}(u,v)<sum_v\times\operatorname{dis}(u,v)\\
\]
也就是 \(2\times sum_v>sum_u\)。其中 \(sum_u\) 表示 \(u\) 的子樹內的軍隊數。顯然這樣的兒子最多只有一個。而如果 \(u\) 不是根，\(u\) 能比 \(fa_u\) 優則 \(fa_u\) 一定沒有 \(u\) 優，所以也就只用考慮兒子，不用考慮父親。
這個做法的時間復雜度顯然和樹的深度有關。因此我們建點分樹，將樹的深度控制在 \(O(\log n)\) 級別。
此時的思路還是一樣的：從根開始，找到自己在原樹上的更優的兒子，然后在點分數上走到包含那個兒子的子樹。沒有更優的兒子說明自己就是最優決策點。
在點分數上對每個點維護子樹軍隊數，子樹軍隊數乘距離，以及子樹軍隊數到父親的距離。這樣對于每個決策點，計算答案就是 \(O(\log n)\) 的，從而總時間復雜度為 \(O(20n\log^2n)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5,inf=1e18;
int n,m;
vector<pii> e[maxn],E[maxn];
namespace LCA{
int dfn[maxn],cnt,dep[maxn];
int oula[maxn<<1],idx[maxn<<1];
il void dfs(int u,int fa){
dfn[u]=++cnt;
idx[cnt]=u;
oula[cnt]=cnt;
for(pii i:e[u]){
int v=i.fir,w=i.sec;
if(v==fa){
continue;
}
dep[v]=dep[u]+w;
dfs(v,u);
oula[++cnt]=dfn[u];
}
}
struct{
int Log[maxn<<1],st[maxn<<1][22];
il void build(){
for(int i=2;i<=cnt;i++){
Log[i]=Log[i>>1]+1;
}
for(int i=1;i<=cnt;i++){
st[i][0]=oula[i];
}
for(int j=1;j<=Log[cnt];j++){
for(int i=1;i+(1<<j)-1<=cnt;i++){
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
}
il int query(int l,int r){
int p=Log[r-l+1];
return min(st[l][p],st[r-(1<<p)+1][p]);
}
}ST;
il void init(){
dfs(1,0);
ST.build();
}
il int lca(int u,int v){
if(dfn[u]>dfn[v]){
swap(u,v);
}
return idx[ST.query(dfn[u],dfn[v])];
}
il int dis(int u,int v){
return dep[u]+dep[v]-dep[lca(u,v)]*2;
}
}
using LCA::dis;
int sz[maxn],mxs[maxn],fa[maxn];
bool ban[maxn];
vector<int> dv;
il void dfs1(int u,int fa,int tot){
sz[u]=1,mxs[u]=0;
for(pii i:e[u]){
int v=i.fir;
if(v==fa||ban[v]){
continue;
}
dfs1(v,u,tot);
sz[u]+=sz[v];
mxs[u]=max(mxs[u],sz[v]);
}
mxs[u]=max(mxs[u],tot-sz[u]);
}
il void dfs2(int u,int fa){
dv.pb(u);
for(pii i:e[u]){
int v=i.fir;
if(v==fa||ban[v]){
continue;
}
dfs2(v,u);
}
}
il int build(){
dfs1(dv[0],0,dv.size());
int rt,tmp=inf;
for(int u:dv){
if(tmp>mxs[u]){
tmp=mxs[u],rt=u;
}
}
ban[rt]=1;
for(pii i:e[rt]){
int v=i.fir;
if(ban[v]){
continue;
}
dv.clear();
dfs2(v,0);
int tmp=build();
E[rt].pb(mp(v,tmp));
fa[tmp]=rt;
}
return rt;
}
int sum[maxn],sumd[maxn],sumf[maxn];
il void upd(int u,int x){
sum[u]+=x;
for(int i=u;fa[i];i=fa[i]){
sum[fa[i]]+=x;
int tmp=dis(u,fa[i]);
sumd[fa[i]]+=x*tmp;
sumf[i]+=x*tmp;
}
}
il int calc(int u){
int res=sumd[u];
for(int i=u;fa[i];i=fa[i]){
res+=sumd[fa[i]]-sumf[i];
res+=(sum[fa[i]]-sum[i])*dis(u,fa[i]);
}
return res;
}
il int query(int u){
int res=calc(u);
for(pii i:E[u]){
if(calc(i.fir)<res){
return query(i.sec);
}
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
e[u].pb(mp(v,w));
e[v].pb(mp(u,w));
}
LCA::init();
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// cout<<dis(i,j)<<" ";
// }
// puts("");
// }
for(int i=1;i<=n;i++){
dv.pb(i);
}
int rt=build();
while(m--){
int u,x;
cin>>u>>x;
upd(u,x);
cout<<query(rt)<<"\n";
}
return 0;
}
}
signed main(){return asbt::main();}
3.「HNOI2015」開店
是道簡單題，建出點分樹后預處理分治子樹對自己和父親的貢獻，查詢暴力爬樹即可。但是用數據結構會因為常數過大喜提 60 分，考慮到是個靜態問題，將子樹信息排序后存成 vector，查詢二分即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
#define pii pair<int,int>
#define fir first
#define sec second
#define mp make_pair
#define lwrb lower_bound
#define uprb upper_bound
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1.5e5+5;
int n,m,A,a[maxn];
vector<pii> e[maxn];
namespace LCA{
int cnt,dfn[maxn],dep[maxn];
int oula[maxn<<1],idx[maxn<<1];
il void dfs(int u,int fa){
dfn[u]=++cnt;
oula[cnt]=cnt;
idx[cnt]=u;
for(pii i:e[u]){
int v=i.fir,w=i.sec;
if(v==fa){
continue;
}
dep[v]=dep[u]+w;
dfs(v,u);
oula[++cnt]=dfn[u];
}
}
struct{
int Log[maxn<<1],st[maxn<<1][22];
il void build(){
for(int i=2;i<=cnt;i++){
Log[i]=Log[i>>1]+1;
}
for(int i=1;i<=cnt;i++){
st[i][0]=oula[i];
}
for(int j=1;j<=Log[cnt];j++){
for(int i=1;i+(1<<j)-1<=cnt;i++){
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
}
il int query(int l,int r){
int p=Log[r-l+1];
return min(st[l][p],st[r-(1<<p)+1][p]);
}
}ST;
il void init(){
dfs(1,0),ST.build();
}
il int lca(int u,int v){
if(dfn[u]>dfn[v]){
swap(u,v);
}
return idx[ST.query(dfn[u],dfn[v])];
}
il int dis(int u,int v){
return dep[u]+dep[v]-dep[lca(u,v)]*2;
}
}
using LCA::dis;
int tot,fa[maxn],sz[maxn],mxs[maxn];
bool ban[maxn];
pii hp[maxn];
vector<int> dv,nia[maxn][2],jul[maxn][2];
il void dfs1(int u,int fa,int tot){
sz[u]=1,mxs[u]=0;
for(pii i:e[u]){
int v=i.fir;
if(v==fa||ban[v]){
continue;
}
dfs1(v,u,tot);
sz[u]+=sz[v];
mxs[u]=max(mxs[u],sz[v]);
}
mxs[u]=max(mxs[u],tot-sz[u]);
}
template<typename T>il void dfs2(int u,int fa,T x){
x(u);
for(pii i:e[u]){
int v=i.fir;
if(v==fa||ban[v]){
continue;
}
dfs2(v,u,x);
}
}
il void upd(int u,int d){
// cout<<tot<<"\n";
sort(hp+1,hp+tot+1);
nia[u][d].pb(-1),jul[u][d].pb(0);
for(int i=1;i<=tot;i++){
nia[u][d].pb(hp[i].fir),jul[u][d].pb(hp[i].sec);
}
for(int i=1;i<=tot;i++){
jul[u][d][i]+=jul[u][d][i-1];
}
}
il int build(){
dfs1(dv[0],0,dv.size());
int u=0,mns=1e9;
for(int v:dv){
if(mns>mxs[v]){
mns=mxs[v],u=v;
}
}
// for(int v:dv){
// cout<<v<<" ";
// }
// cout<<": "<<u<<"\n";
tot=0,dfs2(u,0,[=](int x){hp[++tot]=mp(a[x],dis(u,x));});
upd(u,0);
ban[u]=1;
for(pii i:e[u]){
int v=i.fir;
if(ban[v]){
continue;
}
dv.clear();
dfs2(v,0,[](int x){dv.pb(x);});
int p=build();
fa[p]=u,tot=0;
dfs2(p,0,[=](int x){hp[++tot]=mp(a[x],dis(u,x));});
upd(p,1);
}
ban[u]=0;
return u;
}
il pii query(int u,int d,int L,int R){
// cout<<x.size()<<"\n";
int l=lwrb(nia[u][d].begin(),nia[u][d].end(),L)-nia[u][d].begin()-1;
int r=uprb(nia[u][d].begin(),nia[u][d].end(),R)-nia[u][d].begin()-1;
// cout<<l<<" "<<r<<"\n";
return mp(jul[u][d][r]-jul[u][d][l],r-l);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>A;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
e[u].pb(mp(v,w));
e[v].pb(mp(u,w));
}
LCA::init();
for(int i=1;i<=n;i++){
dv.pb(i);
}
build();
// for(int i=1;i<=n;i++){
// cout<<fa[i]<<" ";
// }
// puts("");
// for(int i=1;i<=n;i++){
// cout<<nia[i][0].size()<<" "<<jul[i][0].size()<<" ";
// cout<<nia[i][1].size()<<" "<<jul[i][1].size()<<"\n";
// }
int ans=0;
while(m--){
int u,l,r;
cin>>u>>l>>r;
l=(l+ans)%A,r=(r+ans)%A;
if(l>r){
swap(l,r);
}
ans=query(u,0,l,r).fir;
// puts("666");
for(int i=u;fa[i];i=fa[i]){
pii res=query(i,1,l,r);
ans-=res.fir+res.sec*dis(u,fa[i]);
res=query(fa[i],0,l,r);
ans+=res.fir+res.sec*dis(u,fa[i]);
}
cout<<ans<<"\n";
}
return 0;
}
}
signed main(){return asbt::main();}
浙公網安備 33010602011771號