点分治求助 60pts
  • 板块P4178 Tree
  • 楼主___A__
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/26 15:35
  • 上次更新2024/6/26 19:29:19
查看原帖
点分治求助 60pts
275860
___A__楼主2024/6/26 15:35
#include<bits/stdc++.h>
using namespace std;
const int N=4e4+5,V=1e9;
int n,x,id,num[N],siz[N],vis[N],dis[N],node,root;
struct graph{
	int v,w;
};
vector<int>vec;
vector<graph>g[N];
void dfs(int u,int last,int all){
	siz[u]=1,num[u]=0;
	for(auto [v,w]:g[u]){
		if(v!=last&&!vis[v]){
			dfs(v,u,all),siz[u]+=siz[v],num[u]=max(num[u],siz[v]);
		}
	}
	num[u]=max(num[u],all-siz[u]);
	if(num[id]>num[u]){
		id=u;
	}
}
void dfs(int u,int last){
	vec.push_back(dis[u]);
	for(auto [v,w]:g[u]){
		if(v!=last&&!vis[v]){
			dis[v]=dis[u]+w,dfs(v,u);
		}
	}
}
struct valtree{
	int l,r,siz;
	valtree(){
		l=r=siz=0;
	}
}val[N*100];
void pushup(int u){
	val[u].siz=val[val[u].l].siz+val[val[u].r].siz;
}
int query(int u,int l,int r,int x){
	if(val[u].l==val[u].r){
		return val[u].siz;
	}
	int mid=(l+r)>>1;
	if(x<=mid){
		return query(val[u].l,l,mid,x);
	}
	return val[val[u].l].siz+query(val[u].r,mid+1,r,x);
}
void update(int &u,int l,int r,int x,int num){
	if(!u){
		u=++node;
	}
	if(l==r){
		val[u].siz+=num;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid){
		update(val[u].l,l,mid,x,num);
	}
	else{
		update(val[u].r,mid+1,r,x,num);
	}
	pushup(u);
}
int solve(int u,int last,int x){
	vector<int>del;
	vis[u]=1,del.push_back(0),update(root,0,V,0,1);
	int ret=0;
	for(auto [v,w]:g[u]){
		if(v!=last&&!vis[v]){
			dis[v]=w,vec.clear(),dfs(v,u);
			for(int i:vec){
				ret+=query(root,0,V,x-i);
			}
			for(int i:vec){
				update(root,0,V,i,1),del.push_back(i);
			}
		}
	}
	for(int i:del){
		update(root,0,V,i,-1);
	}
	for(auto [v,w]:g[u]){
		if(v!=last&&!vis[v]){
            id=0,dfs(v,u,siz[v]),dfs(id,u,siz[v]),ret+=solve(id,u,x);			
		}
	}
	return ret;
}
int main(){
	cin>>n;
	for(int u,v,w,i=1;i<n;i++){
		cin>>u>>v>>w,g[u].push_back({v,w}),g[v].push_back({u,w});
	}
	num[0]=2e9,dfs(1,1,n),dfs(id,id,n),cin>>x;
	cout<<solve(1,1,x);
}
2024/6/26 15:35
加载中...