2 条题解

  • 1
    @ 2022-8-10 15:26:09

    #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; int n,m,a[10000001],s[10000001],dp[505][505],f[505][505],upd[505],upf[505]; int head[10000001],ne[10000001],to[10000001],id; void add(int x,int y){ to[++id]=y,ne[id]=head[x],head[x]=id; to[++id]=x,ne[id]=head[y],head[y]=id; } void dfs(int u,int fa){ dp[u][0]=f[u][0]=0; dp[u][1]=f[u][1]=a[u]; for(int i=head[u];i;i=ne[i]){ int v=to[i]; if(v==fa) continue; dfs(v,u); for(int j=m;j>=1;j--){ f[u][j]=max(f[u][j],f[v][j-1]); for(int k=j-2;k>=0;k--){ dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k-2]); f[u][j]=max(f[u][j],f[v][k]+dp[u][j-k-1]); f[u][j]=max(f[u][j],dp[v][k]+f[u][j-k-2]); } } } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1,u,v;i<n;i++){ cin>>u>>v; add(u,v); } dfs(1,0); int ans=0; for(int i=1;i<=m;i++){ ans=max(ans,f[1][i]); } cout<<ans; }

    • -1
      @ 2022-8-10 15:24:19
      /********************
      备注:
      ********************/
      #include <map>
      #include <queue>
      #include <stack>
      #include <math.h>
      #include <vector>
      #include <iomanip>
      #include <stdio.h>
      #include <string.h>
      #include <iostream>
      #include <algorithm>
      using namespace std;
      #define LL long long
      const int N = 1e6+10;
      const int INF = 0x3f3f3f3f;
      int n , m , a[N] , s[N] , dp[505][505] , f[505][505] ,upd[505] , upf[505];
      int head[N] , to[N] , ne[N] , id;
      void add(int x , int y)
      {
      	to[++id] = y , ne[id] = head[x] , head[x] = id;
      	to[++id] = x , ne[id] = head[y] , head[y] = id;
      }
      void dfs(int u , int fa)
      {
      	dp[u][0] = f[u][0] = 0;
      	dp[u][1] = f[u][1] = a[u];
      	for(int i = head[u] ; i ; i = ne[i])
      	{
      		int v = to[i];
      		if(v == fa) continue;
      		dfs(v , u);
      		for(int j = m ; j >= 1 ; j--)
      		{
      			f[u][j] = max(f[u][j] , f[v][j-1]);
      			for(int  k = j-2 ; k >= 0 ; k--)
      			{
      				dp[u][j] = max(dp[u][j] , dp[v][k] + dp[u][j-k-2]);
      				f[u][j] = max(f[u][j] , f[v][k] + dp[u][j-k-1]);
      				f[u][j] = max(f[u][j] , dp[v][k] + f[u][j-k-2]);
      			}
      		}
      	}
      }
      int main()
      {
      	cin >> n >> m;
      	for(int i = 1 ; i <= n ; i++)
      		cin >> a[i];
      	for(int i = 1 , u , v ; i < n ; i++)
      	{
      		cin >> u >> v;
      		add(u , v);
      	}
      	dfs(1 , 0);
      	int ans = 0;
      	for(int i = 1 ; i <= m ; i++)
      		ans = max(ans , f[1][i]);
      	cout << ans << endl;
       	return 0;
      }
      • 1

      信息

      ID
      2643
      时间
      3000ms
      内存
      61MiB
      难度
      7
      标签
      递交数
      83
      已通过
      22
      上传者