首页 > 其他分享 >P1099 [NOIP2007 提高组] 树网的核

P1099 [NOIP2007 提高组] 树网的核

时间:2022-10-17 19:44:15浏览次数:48  
标签:树网 NOIP2007 int fa edge maxn P1099

#include<bits/stdc++.h>
using namespace std;
#define edge(i,x) for(int i=h[x]; i; i=nt[i])
#define For(i,x,y) for(int i=x; i<=y; i++)
const int N=1e3;
int n,s,h[N],nt[N*2],to[N*2],w[N*2],cnt;
void add(int x,int y,int z)
{
    nt[++cnt]=h[x]; h[x]=cnt; to[cnt]=y; w[cnt]=z;
}
int p[N],nxt[N];
int d[N],st,maxn,ed;
void dfs1(int x,int fa)
{
    edge(i,x)
    {
        int y=to[i];
        if(y==fa)continue;
        //cout<<x<<" "<<y<<" ";
        d[y]=d[x]+w[i];
       // cout<<d[y]<<endl;
        if(d[y]>maxn)
        {
            maxn=d[y],st=y;
        }
        dfs1(y,x);
    }
}
int w1[N],w2[N];
void dfs2(int x,int fa)
{
    edge(i,x)
    {
        int y=to[i];
        if(y==fa)continue;
        d[y]=d[x]+w[i];
        if(d[y]>maxn)
        {
            maxn=d[y],ed=y;
        }
        p[y]=x;
        dfs2(y,x);
    }
}
void dfs3(int x,int fa)
{
    d[x]=0;
    edge(i,x)
    {
        int y=to[i];
        if(y==fa||y==nxt[x]||y==p[x])continue;
        dfs3(y,x);
        d[x]=max(d[x],d[y]+w[i]);
    }
}
int ans;
int main()
{
    //freopen("text.in","r",stdin);
    cin>>n>>s;
    For(i,1,n-1){
        int A,B,C;
        cin>>A>>B>>C;
        add(A,B,C);
        add(B,A,C);
    }
    st=0,maxn=-1;
    dfs1(1,0);
    //cout<<maxn<<endl;
    maxn=-1;
    memset(d,0,sizeof(d));
    dfs2(st,0);
    //cout<<st<<" "<<ed<<endl;
    int j=ed;
    //for(int i=ed; i; i=p[i])
    //{
    //    cout<<i<<" ";
    //}
    //cout<<endl;
    for(int i=ed; i; i=p[i])
        nxt[p[i]]=i;
    ans=(1<<30);
    //for(int i=ed; i; i=p[i])cout<<d[i]<<" ";
    //cout<<endl;
    for(int i=ed; i; i=p[i])
    {
        while(p[j]&&d[i]-d[p[j]]<=s)j=p[j];
        ans=min(ans,max(d[ed]-d[i],d[j]));
    }
    //cout<<ans<<endl;
    for(int i=ed; i; i=p[i])
        dfs3(i,0),ans=max(ans,d[i]);//,printf("%d ",d[i]);
    //cout<<endl;
    cout<<ans<<endl;
}

标签:树网,NOIP2007,int,fa,edge,maxn,P1099
From: https://www.cnblogs.com/dadidididi/p/16800359.html

相关文章

  • P1005 [NOIP2007 提高组] 矩阵取数游戏 题解
    luogu原题传送门[NOIP2007提高组]矩阵取数游戏题目描述帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的\(n\timesm\)的矩阵,矩阵中的每个元素\(a_{i,j}\)均为非......
  • [NOIP2007 普及组] 纪念品分组
    题目链接:https://www.luogu.com.cn/problem/P1094试题分析:乐乐要进行分组,分组原则是一个组中最多两个数,且两数之和小于给定的上限值,乐乐想找到最少能分多少组。我们发现,这......
  • NC16645 [NOIP2007]矩阵取数游戏
    题目链接题目题目描述帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:1.每次取数时须从每行各取走一个元素,......