2 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=5e5+10; vector<pair<int,int>>G[N]; int d[N], dis, h[N], fa, f[N], v[N]; void dfs1(int x) { v[x]=1; for(auto i:G[x]) { int y=i.first,c=i.second; if(v[y]==1) continue; d[y]=d[x]+c; f[y]=x; if(dis<d[y]) dis=d[y], fa=y; dfs1(y); } } void dfs2(int x) { v[x]=1; for(auto i:G[x]) { int y=i.first,c=i.second; if(v[y]==1) continue; dfs2(y); h[x]=max(h[x], h[y]+c); } } int main() { int n,S; scanf("%d%d", &n, &S); for(int i=1,x,y,c; i<n; i++) { scanf("%d%d%d", &x, &y, &c); G[x].push_back({y,c}); G[y].push_back({x,c}); } int l, r; memset(v, 0, sizeof(v)); d[1]=0;f[1]=0; dis=0; dfs1(1); l=fa; memset(v, 0, sizeof(v)); d[l]=0;f[l]=0; dis=0; dfs1(l); r=fa; memset(v, 0, sizeof(v)); memset(h, 0, sizeof(h)); for(int i=r; i; i=f[i]) v[i]=1; int maxh=0; for(int i=r; i; i=f[i]) dfs2(i), maxh=max(maxh, h[i]); int ans=(1LL<<31)-1; for(int i=r, j=r; i; i=f[i]) { while(d[j]-d[i]>S) j=f[j]; ans=min(ans, max({maxh, d[i]-d[l], d[r]-d[j]})); } printf("%d\n", ans); return 0; } -
0
#include<bits/stdc++.h> using namespace std; const int N=5e5+10; vector<pair<int,int>>G[N]; int d[N], dis, h[N], fa, f[N]; bool v[N]; void dfs1(int x) { v[x]=1; for(auto i:G[x]) { int y=i.first,c=i.second; if(v[y]==1) continue; d[y]=d[x]+c; f[y]=x; if(dis<d[y]) dis=d[y], fa=y; dfs1(y); } } void dfs2(int x) { v[x]=1; for(auto i:G[x]) { int y=i.first,c=i.second; if(v[y]==1) continue; dfs2(y); h[x]=max(h[x], h[y]+c); } } int main() { int n,S; scanf("%d%d", &n, &S); for(int i=1,x,y,c; i<n; i++) { scanf("%d%d%d", &x, &y, &c); G[x].push_back({y,c}); G[y].push_back({x,c}); } int l, r; memset(v, 0, sizeof(v)); d[1]=0;f[1]=0; dis=0; dfs1(1); l=fa; memset(v, 0, sizeof(v)); d[l]=0;f[l]=0; dis=0; dfs1(l); r=fa; memset(v, 0, sizeof(v)); memset(h, 0, sizeof(h)); for(int i=r; i; i=f[i]) v[i]=1; int maxh=0; for(int i=r; i; i=f[i]) dfs2(i), maxh=max(maxh, h[i]); int ans=(1LL<<31)-1; for(int i=r, j=r; i; i=f[i]) { while(d[j]-d[i]>S) j=f[j]; ans=min(ans, max({maxh, d[i]-d[l], d[r]-d[j]})); } printf("%d\n", ans); return 0; }
- 1
信息
- ID
- 1439
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 192
- 已通过
- 25
- 上传者