使用双向图，以任意结点为根节点来进行一次dfs。
在dfs过程中，求出以子节点和父亲节点为根的 树的结点数，其中父亲节点为 n - cnt(子节点)

#include <iostream>
#include <string.h>

using namespace std;
const int N = 1e5+5;
int h[N], e[N * 2], ne[N * 2];
bool visit[N];
int idx;
int n;

void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
int res = 1e9;
int dfs(int u){//结点数

    int cnt = 1;
    int ans = 0;
    //visit[u] = true;//设置已访问
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(visit[j]) continue;
        visit[j] = true;
        int tmp = dfs(j);//没必要恢复现场。若恢复 相当于再重复计算一次父亲节点数
        cnt += tmp;
        ans = max(ans, tmp);
    }
    ans = max(ans, n - cnt);//父亲节点肯定是一整个联通块（只能有一个父亲）
    /*
    举个栗子，假设主函数调用的是dfs（1），按照上面那个图，会以1这个点通过for来遍历邻接点，
    会有s=dfs(2),s=dfs(4),s=dfs(7)，你可以求出以1为重心的所有连通块的最大值，但是我刚才
    写的有一个s=dfs(2),你在dfs(2)的时候只能求出来2的所有未被访问的邻接点，也就是只能求
    出来dfs(5)和dfs(8)，求不出来以1为根的这个联通块的数量，这时候就只能通过总结点数n减
    去以2为根节点的数量来求出，也就是n-sum，然后在取一个max(n-sum,res)，就是以2为重心的
    最大连通块数量，这个难就难想在他是通过以一个点为起点开始递归，在递归的过程中求出res，
    再用res来更新ans，yxctql！
    */
    //对于首次遍历的节点来说是没必要的；但对后续的子节点dfs时由于已经过滤掉其父节点了，
    //for循环中就不能获取到以父节点为根的子树，这种情况就需要max(n-sum,res)来保证
    res = min(res, ans);
    return cnt;
}

int main(){

    cin>>n;

    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i ++){
        int a, b;
        cin>>a>>b;
        add(a, b);
        add(b, a);
    }

    visit[2] = true;
    dfs(2);
    cout<<res;
    return 0;
}

#include <iostream>

using namespace std;

const int N = 1005 * 32, V = 2005;

int v[N], w[N], s[N];
int f[V];

int main(){
    int n, m;
    cin>>n>>m;


    int cnt = 0;
    for(int i = 0; i < n; i ++){//这里不是将其转为二进制
                                //而是转为1，2，4，8等的堆，这些堆任意组合可以组成1～c中的任何数
        int a, b, c;

        cin>>a>>b>>c;
        int k = 1;

        while(k <= c){
            cnt ++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            c -= k;
            k *= 2;

        }
        if(c > 0){
            cnt ++;
            v[cnt] = a * c;
            w[cnt] = b * c;
        }
    }

    //01
    for(int i = 1; i <= cnt; i ++){
        for(int j = m; j >= v[i]; j --){
            // f[i][j] = f[i - 1][j];
            // if(j >= v[i])
                f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    cout<<f[m];
    return 0;
}

1. 非递归版本

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == nullptr) return res;

        vector<int> path;
        queue<TreeNode*> que;
        que.push(root);

        while(que.size()){
            int len = que.size();

            for(int i = 0; i < len; i ++){
                auto tmp = que.front();
                que.pop();
                path.push_back(tmp->val);
                if(tmp->left) que.push(tmp->left);
                if(tmp->right) que.push(tmp->right);
            }
            res.push_back(path);
            path.clear();
        }
        return res;
    }
};

1. spfa

const int inf = 0x3f3f3f3f;
class Solution {
public:
    struct Node{
        int x, y, d;
         bool operator< (const Node& b){
             return d < b.d;
         }
    };
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    //转化为求最短路问题
    int minimumObstacles(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        queue<Node> que;
        vector<vector<int>> dist(n + 5, vector<int>(m + 5, inf));
        vector<vector<bool>> st(n + 5, vector<bool>(m + 5));//记录que中的元素
        que.push({0, 0, 0});
        dist[0][0] = 0;
        st[0][0] = true;
        while(que.size()){
            auto tmp = que.front();
            que.pop();
            st[tmp.x][tmp.y] = false;

            for(int i = 0; i < 4; i ++){
                int s = tmp.x + dx[i], t = tmp.y + dy[i];
                if(s < 0 || t < 0 || s >= n || t >= m) continue;

                if(dist[s][t] > dist[tmp.x][tmp.y] + grid[s][t]){
                    dist[s][t] = dist[tmp.x][tmp.y] + grid[s][t];
                    if(! st[s][t]){
                        que.push({s, t, dist[tmp.x][tmp.y] + grid[s][t]});
                        st[s][t] = true;
                    }


                }
            }

        }
        return dist[n - 1][m - 1];
    }
};

2. dijkstra

const int inf = 0x3f3f3f3f;
class Solution {
public:
    struct Node{
        int x, y, d;
         bool operator > (const Node& b) const{
             return d > b.d;
         }
    };
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    //转化为求最短路问题
    int minimumObstacles(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();

        //dijk
        priority_queue<Node, vector<Node>, greater<Node>> pque;
        vector<vector<int>> dist(n + 5, vector<int>(m + 5, inf));
        vector<vector<bool>> st(n + 5, vector<bool>(m + 5));//记录已经计算完毕的元素

        pque.push({0, 0, 0});
        dist[0][0] = 0;
        while(pque.size()){
            auto tmp = pque.top();
            pque.pop();

            if(st[tmp.x][tmp.y]) continue;

            st[tmp.x][tmp.y] = true;
            for(int i = 0; i < 4; i ++){
                int s = tmp.x + dx[i], t = tmp.y + dy[i];
                if(s < 0 || t < 0 || s >= n || t >= m) continue;
                if(dist[s][t] > dist[tmp.x][tmp.y] + grid[s][t]){
                    dist[s][t] = min(dist[s][t], dist[tmp.x][tmp.y] + grid[s][t]);
                    pque.push({s, t, dist[s][t]});
                }

            }   
        }
        return dist[n - 1][m - 1];
    }
};

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        //首先放最大频率的元素，每行空位个数为n + 1,总行数为maxn
        //每行依次放元素
        //A B D
        //A B D
        //... 
        //A B
        //所以长度为(maxn - 1) * (n + 1) + k,这是有空位的情况
        //
        //考虑 1.频率为maxn的元素个数k大于n + 1时；2.剩余字母怎么排
        //第一种情况直接在矩阵后增加列
        //第二种剩余字母，直接在空位自上到下排；若空位不够，往后增加列（需要多少增加多少，不一定增加整条列，这种情况会没有空位！所以这种情况长度一定等于字母总量！）
        //所以综上，res等于max（有空位，无空位），无空位情况也就是数组的长度

        unordered_map<char, int> hash;
        int maxn = 0, cnt = 0;
        for(auto c: tasks) {
            hash[c] ++;
            maxn = max(maxn, hash[c]);
        }
        for(auto [k, v]: hash){
            if(v == maxn) cnt ++;
        }
        int res = max((maxn - 1) * (n + 1) + cnt, (int)tasks.size());
        return res;
    }
};

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        //单调栈
        stack<int> sta;

        for(int i = n - 1; i >= 0; i --){
            //维护一个单调递减的栈
            while(sta.size() && temperatures[sta.top()] <= temperatures[i]) sta.pop();//栈中小于等于ti的永远不会再输出
            if(sta.size())
                ans[i] = sta.top() - i;
            sta.push(i);

        }
        return ans;
    }
};

class Solution {
public:
//将数组分为三个区间    
    //左侧区间满足条件：1. 递增 2. 左边最后一个元素小于右边区间的最小值
    //先满足第一个条件，再将l向左移动（使左边区间满足条件2）
    //同理，处理r
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        //先将l和r移动到区间满足条件1的位置
        while(l + 1 < n && nums[l] <= nums[l + 1]) l ++;
        if(l == n - 1) return 0;
        while(r - 1 >= 0 && nums[r] >= nums[r - 1]) r --;

        //移动l
        for(int i = l + 1; i < n; i ++){
            while(l >= 0 && nums[l] > nums[i]) l --;
        }
        //移动r
        for(int i = r - 1; i >= 0; i --){
            while(r < n && nums[r] < nums[i]) r ++;
        }

        return r - l - 1;//l 和 r分别为左区间的最右，右区间的最左，所以中间区间大小为r-l-1
    }   
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        dfs(root);
        return root;
    }

    void dfs(TreeNode* root){
        if(!root) return ;
        dfs(root->right);//中序遍历，先遍历右子树，保证大于当前节点的已经遍历完！
        sum += root->val;
        root->val = sum;
        dfs(root->left);
    }
};

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        //对于元素numsi，将其对应的下标取反（真正的值可以取绝对值）
        //最终大于0的元素，其下标值为消失的数字
        for(auto x: nums){
            int tmp = abs(x) - 1;
            if(nums[tmp] > 0)
                nums[tmp] *= -1;
        }
        vector<int> res;
        for(int i = 0; i < nums.size(); i ++){
            if(nums[i] > 0) res.push_back(i + 1);
        }
        return res;
    }
};

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        //使用绝对值，
        //每次将元 素值对应的下标 的 元素 取反
        vector<int> res;
        for(auto c: nums){
            int tmp = abs(c) - 1;// -1因为nums从0开始
            nums[tmp] *= -1;
            if(nums[tmp] > 0) res.push_back(abs(c));//大于0说明对nums[tmp]取反了两次，即c重复
        }
        return res;
    }
};