题目链接：P1099 树网的核
树形(dp)。
不会，连暴力(O(n^3))都不会。
只有(64;pts)(似乎能(80)?)。
暴力：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=305;
int d[MAXN],dis[MAXN],ms,md=0,c=1;
int disl[MAXN],disr[MAXN],id[MAXN],rt[MAXN];
int ans=2147483647;
struct node
{
int l,to,nxt;
}e[MAXN<<1];
int head[MAXN],cnt=0;
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].l=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int n,m,l,r,z;
void dfs1(int cur,int fa,int step)
{
dis[cur]=step;
for(int i=head[cur];i;i=e[i].nxt)
{
int j=e[i].to;
if(j!=fa) dfs1(j,cur,step+e[i].l);
}
if(dis[cur]>md) md=dis[cur],ms=cur;
return;
}
void dfs2(int cur)
{
for(int i=head[cur];i;i=e[i].nxt)
{
int j=e[i].to;
if(dis[j]<dis[cur]) d[++c]=j,dfs2(j);
}
return;
}
void dfs3(int cur,int fa,int step)
{
disl[cur]=step;
for(int i=head[cur];i;i=e[i].nxt)
{
int j=e[i].to;
if(j!=fa) dfs3(j,cur,step+e[i].l);
}
return;
}
void dfs4(int cur,int fa,int step)
{
disr[cur]=step;
for(int i=head[cur];i;i=e[i].nxt)
{
int j=e[i].to;
if(j!=fa) dfs4(j,cur,step+e[i].l);
}
return;
}
int ee(int l,int r,int lfa,int rfa,int sum)
{
int maxn=max(min(disl[l],disl[r]),min(disr[l],disr[r]));
for(int i=head[l];i;i=e[i].nxt)
{
int j=e[i].to;
if(sum>=e[i].l&&j!=lfa) maxn=min(maxn,ee(j,r,l,rfa,sum-e[i].l));
}
for(int i=head[r];i;i=e[i].nxt)
{
int j=e[i].to;
if(sum>=e[i].l&&j!=rfa) maxn=min(maxn,ee(l,j,lfa,r,sum-e[i].l));
}
return maxn;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&l,&r,&z);
add(l,r,z);
add(r,l,z);
}
dfs1(1,0,0);
memset(dis,0,sizeof(dis));
md=0;
dfs1(ms,0,0);
d[1]=ms;
dfs2(ms);
disl[d[1]]=0;
dfs3(d[1],0,0);
disr[d[c]]=0;
dfs4(d[c],0,0);
for(int i=1;i<=n;i++) ans=min(ans,ee(i,i,0,0,m));
printf("%d
",ans);
return 0;
}
正解：
#include<cstdio>
#include<algorithm>
#define M 500005
using namespace std;
int n,m,x,y,z,k,id,top,ans=2e9;
int dis[M],fa[M],head[M];
bool mark[M];
struct edge
{
int to,w,nxt;
}E[M<<1];
void add(int u,int v,int w)
{
E[++id]=((edge){v,w,head[u]});
head[u]=id;
}
void dfs(int f,int x){
fa[x]=f;
if(dis[x]>dis[k])k=x;
for(int i=head[x];i;i=E[i].nxt)
{
int y=E[i].to;
if(y==f||mark[y]) continue;
dis[y]=dis[x]+E[i].w;
dfs(x,y);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
dis[1]=1,dfs(0,1);
dis[k]=0,dfs(0,k);
top=k;
for(int i=top,j=top,l=1,r=0;i;i=fa[i])
{
while(dis[j]-dis[i]>m) j=fa[j];
x=max(dis[top]-dis[j],dis[i]);
ans=min(ans,x);
}
for(int i=top;i;i=fa[i]) mark[i]=1;
for(int i=top;i;i=fa[i])
{
k=i,dis[k]=0;
dfs(fa[i],i);
}
for(int i=1;i<=n;i++) ans=max(ans,dis[i]);
printf("%d
",ans);
return 0;
}
大概就是直径上尺取，然后有两种情况，具体看题解去吧。