社区讨论

rt

P4178Tree参与者 12已保存回复 12

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
12 条
当前快照
1 份
快照标识符
@mkhozij6
此快照首次捕获于
2026/01/17 10:32
上个月
此快照最后确认于
2026/01/17 16:52
上个月
查看原帖
CPP
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
using namespace std;
const int maxn=40005;
int vis[maxn];
int g[maxn];
int f[maxn];
int n,m;
int minw;
int root;
int cntg;
int cntf;
int ans;
struct node{
	int x;
	int w;
};
vector<node> a[maxn];
int dfs1(int x,int fa){
	int sze=1;
	int l=a[x].size();
	for(int i=0;i<l;i++){
		int nx=a[x][i].w;
		if(nx!=fa&&!vis[nx]) sze+=dfs1(nx,x); 
	}
	return sze;
}
int dfs2(int x,int fa,int num){
	int sze=1;
	int w=0;
	int l=a[x].size();
	for(int i=0;i<l;i++){
		int nx=a[x][i].x;
		if(nx!=fa&&!vis[nx]){
			int sz=dfs2(nx,x,num);
			if(sz>w) w=sz;
			sze+=sz;
		}
	}
	w=max(num-sze,w);
	if(w<minw){
		minw=w;
		root=x;
	}
	return sze;
}
void dfs3(int x,int fa,int dis){
	g[++cntg]=dis;
	int l=a[x].size();
	for(int i=0;i<l;i++){
		int nx=a[x][i].x;
		if(nx!=fa&&!vis[nx]) dfs3(nx,x,dis+a[x][i].w);
	}
}
void dfs4(int x){
	cntf=1;
	f[0]=0;
	root=x;
	minw=dfs1(x,0)-1;
	dfs2(x,0,minw+1);
	vis[root]=1;
	int l=a[root].size();
	for(int i=0;i<l;i++){
		int nx=a[root][i].x;
		if(!vis[nx]){
			dfs3(nx,0,a[root][i].w);
			sort(g+1,g+cntg+1);
			for(int j=1;j<=cntg;j++){
				int p=upper_bound(g+1,g+cntg+1,m-g[j])-g-j-1;
				if(p<=0) break;
				ans-=p;
			}
			for(int j=1;j<=cntg;j++) f[++cntf]=g[j];
			cntg=0;
		}
	}
	sort(f+1,f+cntf+1);
	for(int i=1;i<=cntf;i++){
		int p=upper_bound(f+1,f+cntf+1,m-f[i])-f-i-1;
		if(p<=0) break;
		ans+=p;
	}	
	for(int i=0;i<l;i++){
		int nx=a[root][i].x;
		if(!vis[nx]) dfs4(nx); 
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y,w;
		cin>>x>>y>>w;
		a[x].push_back({y,w});
		a[y].push_back({x,w});
	}
	cin>>m;
	dfs4(1);
	cout<<ans;
	return 0;
}

回复

12 条回复,欢迎继续交流。

正在加载回复...