学步园

#include<iostream>
#include <vector>
using namespace std;
void dfs(vector<vector<int> > &edges,vector<vector<int> > &tree,int p,int n){
  for(int i=0;i<edges[n].size();i++){
    int j=edges[n][i];
    if(p==j) continue;
    tree[n].push_back(j);
    dfs(edges,tree,n,j);
  }
}
void maxTree(vector<vector<int> > &tree,vector<int> &p,vector<vector<int> > &mLs,int n,int M){//@error: &mLs not mLs
  if(M>1)//@error
    for(int i=0;i<tree[n].size();i++){
    int j=tree[n][i];
    maxTree(tree,p,mLs,j,M-1);
  }
  mLs[n].resize(M+1,0);
  //mLs[n][1]=p[n];
  for(int i=0;i<tree[n].size();i++){
    int u=tree[n][i];
    vector<int> tmp=mLs[n];
    for(int k=1;k<mLs[u].size();k++){
      int w=mLs[u][k];
      for(int j=M-1;j>=k;j--){//@error:M-1 not M
        tmp[j]=max(tmp[j],w+mLs[n][j-k]);
      }
    }
    mLs[n]=tmp;
  }
  for(int i=M;i>0;i--) mLs[n][i]=mLs[n][i-1]+p[n];
  mLs[n][0]=0;
}
int main(){
  int N,M;
  cin>>N>>M;
  vector<vector<int> >edges(N,vector<int>());
  vector<vector<int> >tree(N,vector<int>());
  vector<int>p(N,0);
  for(int i=0;i<N;i++) {int a;cin>>a;p[i]=a;}
  for(int i=0;i<N-1;i++){int a,b;cin>>a>>b;a--,b--;edges[a].push_back(b);edges[b].push_back(a);}
  dfs(edges,tree,-1,0);
  vector<vector<int> > mLs(N,vector<int>());
  maxTree(tree,p,mLs,0,M);
  cout<<mLs[0][M]<<endl;
  return 0;
}

• 首先需要把无向图树形化（dfs），edges[][]=>tree[][]

• 然后maxtree树形递归：

先求出子树们的k节点子树最大权值：mLs[child][nodeNum<M], 

然后对child[]进行合并，关键在于对子树mLs[child][]进行分组背包：每个mLs[child][]是一个物品分组，只能选一个加入最终背包。

1.2 改进上面的分组背包过程:

用下面语句： 

mLs[n][j]=max{mLs[n][j-k]+mLs[u][k]}, 

for u=node.child[0] to child[x]: //某个子树u，看做一个背包的物品分组 mLs[u][1~M-1]

     j=M to 2:  //注意j从大到小迭代，因为小端mLs[n][j-k]尚未循环到，所以未装入分组的物品。在mLs[n][j-k]基础上装，可保证k-loop最后最多装入一次，不会把同分组物品重复放入mLs[n][j].

         k=1 to j-1:// 尝试装入该物品分组中的物品到mLs[n][j]

            mLs[n][j]=max(mLs[n][j],mLs[n][j-k]+mLs[u][k])

#include<iostream>
#include <vector>
using namespace std;
void maxTree(vector<vector<int> > &tree,vector<int> &p,vector<vector<int> > &mLs,int n,int M){//@error: &mLs not mLs 
  mLs[n].resize(M+1,0);
  if(M==0) return;//@error: stop condition of dfs!!or mLs[n][1] below will overflow!!
  
  for(int i=0;i<tree[n].size();i++) 
    maxTree(tree,p,mLs,tree[n][i],M-1);//@error: M-1 since son has M-1 nodes in the most

  mLs[n][1]=p[n];////@error: need this edge-condition init
  for(int i=0;i<tree[n].size();i++){
    int u=tree[n][i];
    //下面是一个巧妙的分组背包，关键是j的迭代顺序为从大到小
    for(int j=M;j>1;j--){//@error:M to 2, not to 1(as edge-condition init), in the dp procession
      for(int k=1;k<j;k++){
        mLs[n][j]=max(mLs[n][j],mLs[n][j-k]+mLs[u][k]);//@error: remember k-loop only change mLs[n][j],not mLs[n][j-k],so it is right here
      }//from dp we see, a simple/partial and high-compressed image is best for human-brain's timely and memory-saving calculation.
    }
  }
}
int main(){
  int N,M; cin>>N>>M;
  vector<int>p(N,0);
  vector<vector<int> >tree(N,vector<int>());
  for(int i=0;i<N;i++) {int a;cin>>a;p[i]=a;}
  for(int i=0;i<N-1;i++){int a,b;cin>>a>>b;a--,b--;tree[a].push_back(b);}
  vector<vector<int> > mLs(N,vector<int>());
  maxTree(tree,p,mLs,0,M);
  cout<<mLs[0][M]<<endl;
  return 0;
}

2.树动规找树直径:

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第一行为一个整数N，意义如前文所述。

每组测试数据的第2~N行，每行分别描述一根木棍，其中第i+1行为两个整数Ai，Bi，表示第i根木棍连接的两个小球的编号。

对于20%的数据，满足N<=10。

对于50%的数据，满足N<=10^3。

对于100%的数据，满足N<=10^5，1<=Ai<=N, 1<=Bi<=N

#include <iostream>
#include <queue>
using namespace std;

int dfs(vector<vector<int> >&egs,int root,int &mNum){
    priority_queue<int> que;
    for(int i=0;i<egs[root].size();i++){
        int v=egs[root][i];
        que.push(dfs(egs,v,mNum));
    }
    int m=0;int n=0;
    if(!que.empty()) m+=1+que.top(),n+=1+que.top(),que.pop();
    if(!que.empty()) m+=1+que.top(),que.pop();
    mNum=max(m,mNum);
    return n;
}

int main(){
    int N;cin>>N;
    vector<vector<int> > egs(N,vector<int>());
    for(int i=1;i<N;i++){
        int a,b;cin>>a>>b;a--,b--;
        egs[a].push_back(b);
    }
    int mNum=0;
    if(N<1) cout<<0<<endl;
    else {dfs(egs,0,mNum);cout<<mNum<<endl;}
    return 0;
}