2 条题解

  • 0
    @ 2025-10-8 16:57:02
    #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
      @ 2025-10-8 16:56:53
      #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

      *【树形DP:树的直径】树网的核[NOIP提高组2007]

      信息

      ID
      1439
      时间
      1000ms
      内存
      256MiB
      难度
      8
      标签
      递交数
      192
      已通过
      25
      上传者