A（洛谷 ）

第一次错是深搜时候忘记是双向边，导致重复搜索，要判断下父节点
第二次错是忘记绝对值
除了直接dfs还可以用kruskal
//w[i]*(size[i]-(n-size[i]))=w[i]*(size*2-n)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,M=N*2;//连通块,点的一边为size,另一边为n-size
int p[N],h[N],ne[M],w[M],e[M],idx;//w[i]*(size[i]-(n-size[i]))=w[i]*(size*2-n)
LL res=0;
LL num[M];
int n;
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dfs(int u,int k)
{
    num[u]=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(k==j)continue;//因为是双向边,防止回搜
        dfs(j,u);
        num[u]+=num[j];
        res+=(LL)(abs(num[j]*2-n)*w[i]);
    }
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=1;i<=n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    dfs(1,-1);//设-1是1父节点
    cout<<res<<endl;
    return 0;
}

B（洛谷 ）
最大值最小，一眼二分（可惜不会写）看题解

读完题目之后，有一个比较明显的句子“ 整个部队的伤害值最小 。” 因为整个部队的伤害值是最大值那么这个题目就变成了最大值的最小值 所以我们考虑二分答案求解。
我们二分一个答案mid来表示一个界限，如果当前这个格子的伤害代价比mid小则可以走否则就不走，
每次check函数只需判断能否从第一行走到最后一行即可，因为每一行的每个门都是相连的，所以只要有一个能到，
那么我们再派m-1个人顺着这条路过去再沿着横向的门过去就好啦，因为第一行和最后一行的伤害值为零，
所以这么做莫得问题。

#include<bits/stdc++.h>
using namespace std;
const int MaxN = 1005;
const int inf = 0x3f3f3f3f;
const int dx[5] = {0, 1, 0, -1, 0};
const int dy[5] = {0, 0, 1, 0, -1};
int p[MaxN][MaxN], vis[MaxN][MaxN];
int n, m;
int l = inf, r = -inf, mid, ans, f; 
bool bfs(int x, int y, int maxn) //判断mid是否可行的bfs
{
    queue<pair<int, int> > q;
    q.push(make_pair(x, y)); 
    vis[x][y] = 1; 
    while(q.size()) 
    { //以下就是bfs板子
        int xx = q.front().first; 
        int yy = q.front().second;
        q.pop();
        for(int i = 1; i <= 4; i++) 
        {
            int nx = xx + dx[i];
            int ny = yy + dy[i];
            if(nx < 1 || nx > n || yy < 1 || yy > m || vis[nx][ny] || p[nx][ny] > maxn)
                continue; //不可行（越界、已访问、伤害过大）的直接跳过
            vis[nx][ny] = 1;
            if(nx == n) return 1; //到了，返回1
            else q.push(make_pair(nx, ny));
        }
    }
    return 0; //没有搜到，返回0
}

int main()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i++) 
    {
        for(int j = 1; j <= m; j++)
        {
            cin>>p[i][j];
            r = max(r, p[i][j]);
            l = min(l, p[i][j]);
        }
    }
    while(l <= r) { //二分答案模板
        mid = (l + r) >> 1;
        f = 0;
        memset(vis, 0, sizeof(vis)); //重置数组
        if(bfs(1, 1, mid)) r = mid - 1, ans = mid; //如果这个mid可行，说明可能还能再小，于是更新答案 + 缩小范围
        else l = mid + 1; //mid此不可行，说明不可能再小，也缩小范围，不更新答案(因为求最小值)
    }
    printf("%d", ans);
    return 0;
}

C（只会写floyd(O(n^3))）但有更优复杂度（题解 ）

有bfs，深搜二叉树，带权树的重心

#include<bits/stdc++.h>//bfs（好理解，O（n^2））
using namespace std;
const int N = 210,INF = 1e9 + 10;
typedef long long ll;
int val[N],e[N],h[N],ne[N],idx,w[N],d[N];
bool st[N];
int n,res;
void add(int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}
int bfs(int st)
{
    queue<int> q;
    q.push(st);
    memset(d,-1,sizeof d);
    d[st] = 0;
    int sum = 0;
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        for(int i = h[t];i != -1;i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1)//正好省了st判断
            {
                q.push(j);
                d[j] = d[t] + 1;//统计路径
                sum += d[j] * val[j];
            }
        }
    }
    return sum;
}
int main()
{
    cin >> n;
    memset(h,-1,sizeof h);

    for(int i = 1;i <= n;i ++) 
    {
        int l,r;
        cin >> val[i] >> l >> r;
        if(l) add(i,l,1),add(l,i,1);
        if(r) add(i,r,1),add(r,i,1);
    }

    int minn = INF;
    for(int i = 1;i <= n;i ++)//每次从一个节点遍历找最短
    {
        minn = min(minn,bfs(i));
    }
    cout << minn << '\n';
    return 0;
}