专栏文章

题解：P10805 [CEOI 2024] 加油站

SSolwek
P10805题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mimzh3gf
此快照首次捕获于
2025/12/01 18:05
3 个月前
此快照最后确认于
2025/12/01 18:05
3 个月前
查看原文
无脑硬维护做法！
起手套一个点分治，然后考虑每个点分成两种贡献：
  • 子树内的某个节点走向他并且在他这里加油了
  • 点分治根子树外的某个节点走向他并且在他这里加油了
考虑第一个咋做，发现要维护的操作相当于：
  • 插入 xx 个 yy
  • 把 <x<x 的数都变成 yy
  • 全局减 xx
  • 合并
这些东西直接上平衡树用脚维护，不过要注意平衡树有交合并需要把值相同的点缩起来，不然复杂度会寄。
考虑第二个咋做，你发现不能直接套平衡树了，因为如果硬套还需要可持久化，上面这些操作肯定不支持，那么考虑一些其他能可持久化的结构，容易想到主席树。
因为你是从根一直到某个点，所以就不会有合并操作，值域线段树上容易维护前两种操作，因为是单点修改所以可以可持久化，第三种操作因为是全局的，所以直接将整体下标偏移一下即可，那么这个题就做完了！
时间复杂度 O(nlog⁡2nlog⁡v)O(n\log^2n\log v)，常数不大跑的飞快。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=70010,inf=1e14;
int n,k;
vector<pair<int,int> >g[N];
struct node{
	int l,r,x,cnt,s,add;
	unsigned int rk;
};
int frt[N],tot1,tot2,drt[N];
int sz[N],vis[N],ans[N];
struct qwq{
	int l,r,x;
};
struct SEG{
	qwq tr[N<<7];
	void update(int l,int r,int &p1,int p2,int x,int v){
		if(!p1){
			p1=++tot2;
			tr[p1]={0,0,0};
		}
		if(l==r){
			tr[p1].x=tr[p2].x+v;
			return;
		}
		int mid=(l+r)>>1;
		if(x<=mid){
			tr[p1].r=tr[p2].r;
			update(l,mid,tr[p1].l,tr[p2].l,x,v);
		}else{
			tr[p1].l=tr[p2].l;
			update(mid+1,r,tr[p1].r,tr[p2].r,x,v); 
		} 
		tr[p1].x=tr[tr[p1].l].x+tr[tr[p1].r].x;
	}
	int query(int l,int r,int p,int a,int b){
		if(!p)return 0;
		if(l>b||r<a)return 0;
		if(a<=l&&r<=b)return tr[p].x;
		int mid=(l+r)>>1;
		return query(l,mid,tr[p].l,a,b)+query(mid+1,r,tr[p].r,a,b);
	}
}P; 
struct FHQ{
	node tr[N<<4];
	void updadd(int p,int v){
		tr[p].x+=v;
		tr[p].add+=v;
	}
	void pushdown(int p){
		if(tr[p].add){
			updadd(tr[p].l,tr[p].add);
			updadd(tr[p].r,tr[p].add);
			tr[p].add=0;
		}		
	}
	void pushup(int p){
		tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+tr[p].cnt;
		if(tr[p].x==tr[tr[p].l].x)
			tr[p].cnt+=tr[tr[p].l].cnt,tr[p].l=merge(tr[tr[p].l].l,tr[tr[p].l].r);
		else if(tr[p].x==tr[tr[p].r].x)
			tr[p].cnt+=tr[tr[p].r].cnt,tr[p].r=merge(tr[tr[p].r].l,tr[tr[p].r].r);
	}
	void spilt(int v,int p,int &x,int &y){
		if(!p){
			x=y=0;
			return;
		}
		pushdown(p);
		if(tr[p].x<=v){
			x=p;
			spilt(v,tr[p].r,tr[p].r,y);
		}else{
			y=p;
			spilt(v,tr[p].l,x,tr[p].l);
		}
		pushup(p);
	}
	int merge(int x,int y){
		if(!x||!y)return x|y;
		pushdown(x);pushdown(y);
		if(tr[x].rk<tr[y].rk){
			int L=0,R=0;
			spilt(tr[x].x,y,L,R);
			tr[x].l=merge(tr[x].l,L);
			tr[x].r=merge(tr[x].r,R);
			pushup(x);
			return x;
		}else{
			int L=0,R=0;
			spilt(tr[y].x,x,L,R);
			tr[y].l=merge(tr[y].l,L);
			tr[y].r=merge(tr[y].r,R);
			pushup(y);
			return y;
		}
	}
	void insert(int &rt,int x,int kw){
		unsigned int y=1ll*rand()*rand()*rand();
		int L=0,R=0;
		spilt(x,rt,L,R);
		if(tr[L].x!=x){
			tr[++tot1]={0,0,x,kw,kw,0,y};
			L=merge(L,tot1);			
		}else{
			tr[L].cnt+=kw;
			tr[L].s+=kw;
		}
		rt=merge(L,R); 
	}
}T;
int rt,nmx;
void getrt(int u,int f,int tl){
	sz[u]=1;
	int mx=0;
	for(auto v:g[u]){
		if(vis[v.first]||v.first==f)continue;
		getrt(v.first,u,tl);
		sz[u]+=sz[v.first]; 
		mx=max(mx,sz[v.first]);
	}
	mx=max(mx,tl-sz[u]);
	if(mx<nmx){
		rt=u;
		nmx=mx;
	}
}
void clear(int u,int f){
	frt[u]=drt[u]=0;
	for(auto v:g[u]){
		if(vis[v.first]||v.first==f)continue;
		clear(v.first,u);
	}
}
void dfs1(int u,int f,int w,int val){
	T.insert(frt[u],k,1);
	for(auto v:g[u]){
		if(vis[v.first]||v.first==f)continue;
		dfs1(v.first,u,v.second,val);
		frt[u]=T.merge(frt[u],frt[v.first]);
	}
	int L=0,R=0;
	T.spilt(w-1,frt[u],L,R);
	ans[u]+=val*T.tr[L].s;
	frt[u]=R;
	if(T.tr[L].s)
	T.insert(frt[u],k,T.tr[L].s);
	T.updadd(frt[u],-w);
}
void dfs2(int u,int f,int id,int w,int s){
	int cnt=P.query(0,inf,id,s,s+w-1);
	ans[f]+=cnt*sz[u];
	P.update(0,inf,drt[u],id,k+s,cnt); 
	s+=w;
	for(auto v:g[u]){
		if(vis[v.first]||v.first==f)continue;
		dfs2(v.first,u,drt[u],v.second,s);
	}
}
int dwq;
void dfs3(int u){
	if(!u)return;
	T.pushdown(u); 
	P.update(0,inf,dwq,dwq,T.tr[u].x,T.tr[u].cnt);
	dfs3(T.tr[u].l);
	dfs3(T.tr[u].r);
}
void getsz(int u,int f){
	sz[u]=1;
	for(auto v:g[u]){
		if(v.first==f||vis[v.first])continue;
		getsz(v.first,u);
		sz[u]+=sz[v.first];
	}
}
void solve(int u,int tl){
	nmx=1e9;rt=0;tot1=0;tot2=0;
	getrt(u,0,tl);
	getsz(rt,0);
	for(auto v:g[rt]){
		if(vis[v.first])continue;
		dfs1(v.first,rt,v.second,tl-sz[v.first]);
	}
	dwq=0;
	P.update(0,inf,dwq,dwq,k,1);
	for(int i=0;i<g[rt].size();i++){
		pair<int,int>v=g[rt][i];
		if(vis[v.first])continue;
		dfs2(v.first,rt,dwq,v.second,0);
		dfs3(frt[v.first]);
	}
	dwq=0;
	for(int i=g[rt].size()-1;i>=0;i--){
		pair<int,int>v=g[rt][i];
		if(vis[v.first])continue;
		dfs2(v.first,rt,dwq,v.second,0);
		dfs3(frt[v.first]);
	}
	clear(rt,0);
	for(int i=0;i<=tot1;i++)T.tr[i]={0,0,0,0,0,0,0};
	for(int i=0;i<=tot2;i++)P.tr[i]={0,0,0};
	vis[rt]=1;
	for(auto v:g[rt]){
		if(vis[v.first])continue;
		solve(v.first,sz[v.first]);
	}
}
signed main(){
	srand(time(0)); 
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<n;i++){
		int u,v,w;
		cin>>u>>v>>w;
		u++;v++;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	solve(1,n);
	for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...