#13WA其他全Ac,求条玄关(马蜂良好)
查看原帖
#13WA其他全Ac,求条玄关(马蜂良好)
1294257
zyx_Henry楼主2025/1/31 21:09
#include<bits/stdc++.h>
using namespace std;
int nxt[1000005],to[1000005],weight[1000005],f[5000005],head[500005],fa[500005],visited[500005],arr[500005];
long long dist[500005],dist1[500005],ans1=0,ans2=INT_MAX;
int maxv=0,root=0,tot,a,b;
void add_edge(int u,int v,long long w)
{
    nxt[++tot]=head[u];
    to[tot]=v;
    weight[tot]=w;
    head[u]=tot;
}
void dfs(int u,int pre,int w)
{
    int i,v;
    dist[u]=dist[pre]+w;
    if(dist[u]>maxv)
    {
        maxv=dist[u];
        a=u;
    }
    for(i=head[u];i;i=nxt[i])
    {
        v=to[i];
        if(v==pre)
            continue;
        dfs(v,u,weight[i]);
    }
}
void dfs1(int u,int pre,int w)
{
    int i,v;
    dist[u]=dist[pre]+w;
    fa[u]=pre;
    if(dist[u]>maxv)
    {
        maxv=dist[u];
        b=u;
    }
    for(i=head[u];i;i=nxt[i])
    {
        v=to[i];
        if(v==pre)
            continue;
        dfs1(v,u,weight[i]);
    }
}
void dfs2(int u,int pre,int w)
{
    int i,v;
	dist1[u]=dist1[v]+w;
    for(i=head[u];i;i=nxt[i])
    {
        v=to[i];
        if(v==pre||visited[v])
            continue;
        dfs2(v,u,weight[i]);
		
    }
}
int main()
{
    int n,m,u,v,w,i,j,s;
    scanf("%d %d",&n,&s);
    for(i=1;i<=n-1;++i)
    {
        scanf("%d %d %d",&u,&v,&w);
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    dfs(1,0,0);
    maxv=0;
    memset(dist,0,sizeof(dist));
    dfs1(a,0,0);
    i=b;
    while(i)
    {
        arr[++arr[0]]=i;
        visited[i]=1;
        i=fa[i];
    }
    for(i=1;i<=n;++i)
    {
        if(visited[i])
            dfs2(i,0,0);
    }
    for(i=1;i<=n;++i)
    {
        if(!visited[i])
            ans1=max(ans1,dist1[i]);
    }
    for(i=j=1;i<=arr[0];++i)
    {
        while(abs(dist[arr[i]]-dist[arr[j]])>s)
            ++j;
        f[i]=j;
    }
    for(i=1;i<=arr[0];++i)
    {
        ans2=min(ans2,max(abs(dist[arr[arr[0]]]-dist[arr[i]]),abs(dist[arr[f[i]]]-dist[arr[1]])));
   	}
    printf("%lld",max(ans1,ans2));
    return 0;
}
2025/1/31 21:09
加载中...