点分树模板
- 建立新树，存储信息，强制在线询问
cpp
int n,m,A;
vector<PII> adj[N];
bool st[N];
int age[N];
struct Father{
int u,num,dis;
};
vector<Father> f[N];//所有父亲信息，最多有logn个父亲
struct Son{
int age,dis;
bool operator<(const Son&tmp)const{
return age<tmp.age;
}
};
vector<Son> son[N][3];//所有儿子信息
int get_size(int u,int fa){
if(st[u])return 0;
int res=1;
for(auto [v,w]:adj[u]){
if(v==fa)continue;
res+=get_size(v,u);
}
return res;
}
int get_wc(int u,int fa,int tot,int &wc){
if(st[u])return 0;
int sum=1,ms=0;
for(auto [v,w]:adj[u]){
if(v==fa)continue;
int t=get_wc(v,u,tot,wc);
ms=max(ms,t);
sum+=t;
}
ms=max(ms,tot-sum);
if(ms<=tot/2)wc=u;
return sum;
}
void get_dis(int u,int fa,int dis,int wc,int k,vector<Son>&p){
if(st[u])return;
f[u].push_back({wc,k,dis});
p.push_back({age[u],dis});
for(auto [v,w]:adj[u]){
if(v==fa)continue;
get_dis(v,u,dis+w,wc,k,p);
}
}
void cal(int u){
if(st[u])return;
get_wc(u,0,get_size(u,0),u);
st[u]=true;
int k=0;
for(auto [v,w]:adj[u]){
if(st[v])continue;
auto &p=son[u][k];
p.push_back({-1,0}),p.push_back({A+1,0});//哨兵
get_dis(v,0,w,u,k,p);
k++;
sort(p.begin(),p.end());
for(int i=1;i<p.size();i++)p[i].dis+=p[i-1].dis;
}
for(auto [v,w]:adj[u])cal(v);
}
int query(int u,int l,int r){
int res=0;
for(auto &[fa,num,dis]:f[u]){
int g=age[fa];
if(g>=l&&g<=r)res+=dis;
for(int i=0;i<3;i++){
if(i==num)continue;
auto &p=son[fa][i];
if(p.empty())continue;
int L=lower_bound(p.begin(),p.end(),Son{l,-1})-p.begin();
int R=lower_bound(p.begin(),p.end(),Son{r+1,-1})-p.begin();
res+=dis*(R-L)+p[R-1].dis-p[L-1].dis;
}
}
for(int i=0;i<3;i++){
auto &p=son[u][i];
if(p.empty())continue;
int L=lower_bound(p.begin(),p.end(),Son{l,-1})-p.begin();
int R=lower_bound(p.begin(),p.end(),Son{r+1,-1})-p.begin();
res+=p[R-1].dis-p[L-1].dis;
}
return res;
}
void solve(){
cin>>n>>m>>A;
for(int i=1;i<=n;i++)cin>>age[i];
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
cal(1);
int res=0;
while(m--){
int u,a,b;
cin>>u>>a>>b;
int l=(a+res)%A,r=(b+res)%A;
if(l>r)swap(l,r);
//询问树上年龄在[l,r]的点到u的距离之和
res=query(u,l,r);
cout<<res<<"\n";
}
}