XCPC Notes

Appearance

发布时间：2024-08-24

点分治和点分树 ​

模板 ​

  • 求树内距离小于等于m的点对数
  • 两个点均在某棵子树内
  • 一个点在重心
  • 两个点属于两棵子树
cpp
int n,m;
vector<PII> adj[N];
bool st[N];
int q[N],p[N];
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){//获取重心(不一定是真重心，满足<=n/2即可)
    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_dist(int u,int fa,int dis,int &qt){//获取子树全部dis
    if(st[u])return;
    q[qt++]=dis;
    for(auto [v,w]:adj[u]){
        if(v==fa)continue;
        get_dist(v,u,dis+w,qt);
    }
}
int get(int a[],int k){//计算
    sort(a,a+k);
    int res=0;
    for(int i=k-1,j=-1;i>=0;i--){
        while(j+1<i&&a[j+1]+a[i]<=m)j++;
        j=min(j,i-1);
        res+=j+1;
    }
    return res;
}
int cal(int u){
    if(st[u])return 0;
    int res=0;
    get_wc(u,0,get_size(u,0),u);
    st[u]=true;
    int pt=0;
    for(auto [v,w]:adj[u]){
        int qt=0;
        get_dist(v,0,w,qt);
        res-=get(q,qt);//容斥，减去两个点在同一颗子树的情况
        for(int k=0;k<qt;k++){
            if(q[k]<=m)res++;//重心与子树的点
            p[pt++]=q[k];
        }
    }
    res+=get(p,pt);//总计算
    for(auto [v,w]:adj[u])res+=cal(v);
    return res;
}
void solve(){
    cin>>n;
    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});
    }
    cin>>m;
    cout<<cal(1);
}

P4149 [IOI2011] Race ​

  • 求树内点对距离恰好等于m的边数最少数
cpp
int n,m,ans=1e9;
vector<PII> adj[N];
bool st[N];
PII q[N],p[N];
int f[M];
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){//获取重心(不一定是真重心，满足<=n/2即可)
    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_dist(int u,int fa,int dis,int cnt,int &qt){//获取子树全部dis
    if(st[u]||dis>m)return;
    q[qt++]={dis,cnt};
    for(auto [v,w]:adj[u]){
        if(v==fa)continue;
        get_dist(v,u,dis+w,cnt+1,qt);
    }
}
void cal(int u){
    if(st[u])return;
    int res=0;
    get_wc(u,0,get_size(u,0),u);
    st[u]=true;
    int pt=0;
    for(auto [v,w]:adj[u]){
        int qt=0;
        get_dist(v,0,w,1,qt);
        for(int k=0;k<qt;k++){
            auto &[dis,cnt]=q[k];
            p[pt++]=q[k];
            if(dis==m)ans=min(ans,cnt);
            ans=min(ans,f[m-dis]+cnt);
        }
        for(int k=0;k<qt;k++){
            auto &[dis,cnt]=q[k];
            f[dis]=min(f[dis],cnt);
        }
    }
    for(int k=0;k<pt;k++)f[p[k].first]=1e9;
    for(auto [v,w]:adj[u])cal(v);
}
void solve(){
    cin>>n>>m;
    for(int i=0;i<=1e6;i++)f[i]=1e9;
    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);
    if(ans==1e9)ans=-1;
    cout<<ans<<"\n";
}

P3806 【模板】点分治 1 ​

cpp
int n,m;
vector<PII> adj[N];
bool st[N];
int q[N],p[N];
PII ans[110];
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){//获取重心(不一定是真重心，满足<=n/2即可)
    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_dist(int u,int fa,int dis,int &qt){//获取子树全部dis
    if(st[u])return;
    q[qt++]=dis;
    for(auto [v,w]:adj[u]){
        if(v==fa)continue;
        get_dist(v,u,dis+w,qt);
    }
}
unordered_map<int,bool> f;
void cal(int u){
    if(st[u])return;
    int res=0;
    get_wc(u,0,get_size(u,0),u);
    st[u]=true;
    int pt=0;
    for(auto [v,w]:adj[u]){
        int qt=0;
        get_dist(v,0,w,qt);
        for(int k=0;k<qt;k++){
            int dis=q[k];
            p[pt++]=q[k];
            for(int i=1;i<=m;i++){
                auto &[d,res]=ans[i];
                if(dis==d)res=1;
                if(d-dis>0&&f.count(d-dis))res=1;
            }
        }
        for(int k=0;k<qt;k++){
            f[q[k]]=1;
        }
    }
    f.clear();
    for(auto [v,w]:adj[u])cal(v);
}
void solve(){
    cin>>n>>m;
    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});
    }
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        ans[i]={x,0};
    }
    cal(1);
    for(int i=1;i<=m;i++){
        if(ans[i].second)cout<<"AYE\n";
        else cout<<"NAY\n";
    }
}

P3714(点分治+线段树合并) ​

给你一棵 nn 个点的无根树。

树上的每条边具有颜色。一共有 mm 种颜色，编号为 11 到 mm，第 ii 种颜色的权值为 cic_i。

对于一条树上的简单路径，路径上经过的所有边按顺序组成一个颜色序列，序列可以划分成若干个相同颜色段。定义路径权值为颜色序列上每个同颜色段的颜色权值之和。

请你计算，经过边数在 ll 到 rr 之间的所有简单路径中，路径权值的最大值。

  • 可以预处理出lca为当前根的所有dis对应的val值
  • 那么对于当前的dis，我们只需要之前的查询[l−dis,r−dis][l-dis,r-dis]最大值，可以用线段树维护
  • 但是如果两条路径连接处权值相同，需要减去这个权值
  • 因此我们维护两颗线段树，一个表示与当前初始序列颜色不同，一个相同
  • 当不同时，将相同的合并到不同的上面
  • 记得对于每个邻接表的顶点先按颜色排个序
cpp
vector<int> ls,rs;
vector<int> mx;
int newNode(int x=-INF){
	mx.push_back(x);
	ls.push_back(0);
	rs.push_back(0);
	return ls.size()-1;
}
void clear(){
	mx.clear();
	ls.clear();
	rs.clear();
	newNode();
}
void pushup(int p){
	mx[p]=max(mx[ls[p]],mx[rs[p]]);
}
int merge(int p,int q,int l,int r){
	if(!p)return q;
	if(!q)return p;
	if(l==r){
		mx[p]=max(mx[p],mx[q]);
		return p;
	}
	int mid=l+r>>1;
	ls[p]=merge(ls[p],ls[q],l,mid);
	rs[p]=merge(rs[p],rs[q],mid+1,r);
	pushup(p);
	return p;
}
int insert(int p,int l,int r,int x,int y){
	if(!p)p=newNode();
	if(l==r){
		mx[p]=max(mx[p],y);
		return p;
	}
	int mid=l+r>>1;
	if(x<=mid)ls[p]=insert(ls[p],l,mid,x,y);
	else rs[p]=insert(rs[p],mid+1,r,x,y);
	pushup(p);
	return p;
}
int query(int p,int l,int r,int ql,int qr){
	if(!p)return -INF;
	if(ql<=l&&r<=qr)return mx[p];
	int mid=l+r>>1;
	int res=-INF;
	if(ql<=mid)res=max(res,query(ls[p],l,mid,ql,qr));
	if(qr>mid)res=max(res,query(rs[p],mid+1,r,ql,qr));
	return res;
}
vector<PII> adj[N];
bool st[N];
PII q[N];
int c[N];
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){//获取重心(不一定是真重心，满足<=n/2即可)
    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_dist(int u,int fa,int dis,int val,int lstw,int &qt){//获取子树全部dis
    if(st[u])return;
    q[qt++]={dis,val};
    for(auto [v,w]:adj[u]){
        if(v==fa)continue;
        get_dist(v,u,dis+1,val+(lstw!=w)*c[w],w,qt);
    }
}
int n,m,l,r;
int cal(int u){
    if(st[u])return -INF;
    int res=-INF;
    get_wc(u,0,get_size(u,0),u);
    st[u]=true;
    int pt=0;
	clear();
	array<int,2> root={0,0};
    for(int i=0;i<adj[u].size();i++){
		auto [v,w]=adj[u][i];
		if(i==0||w!=adj[u][i-1].S){
			root[0]=merge(root[0],root[1],1,200000);
			root[1]=0;
		}
        int qt=0;
        get_dist(v,0,1,c[w],w,qt);
		for(int k=0;k<qt;k++){
			auto [dis,val]=q[k];
			if(dis>=l&&dis<=r)res=max(res,val);
			if(dis>r)continue;
			int R=r-dis,L=max(1ll,l-dis);
			if(L>R)continue;
			res=max(res,query(root[0],1,200000,L,R)+val);
			res=max(res,query(root[1],1,200000,L,R)+val-c[w]);
		}
		for(int k=0;k<qt;k++){
			auto [dis,val]=q[k];
			if(dis>r)continue;
			root[1]=insert(root[1],1,200000,dis,val);
		}
    }
    for(auto [v,w]:adj[u])res=max(res,cal(v));
    return res;
}
void solve(){
	cin>>n>>m>>l>>r;
	for(int i=1;i<=m;i++)cin>>c[i];
	for(int i=1;i<n;i++){
		int u,v,w;
		cin>>u>>v>>w;
		adj[u].emplace_back(v,w);
		adj[v].emplace_back(u,w);
	}
	for(int i=1;i<=n;i++){
		ranges::sort(adj[i],[&](const auto &x,const auto &y){
			return x.S<y.S;
		});
	}
	cout<<cal(1)<<"\n";
}

点分树模板(P3241 [HNOI2015] 开店) ​

  • 建立新树，存储信息，强制在线询问
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){// 询问age在[l,r]的到点u的距离和
    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";
    }
}

P6329 【模板】点分树 | 震波 ​

  • 0 x k求距离x小于等于k的点权和
  • 1 x y将val[x]修改成y

Wenwei Lin · 2022 — 2025