社区讨论
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 条回复,欢迎继续交流。
正在加载回复...