小G有一个大树

解题思路

大佬题解

AC代码

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e6+10;
int sum=inf,node,n,w[N];
vector<int> tree[N];
void dfs(int x,int fa) {
    int maxx=0;
    w[x]=1;
    for(int i=0;i<tree[x].size();i++) {
        int tx=tree[x][i];
        if(tx==fa) continue;
        dfs(tx,x);
        w[x]+=w[tx];
        maxx=max(maxx,w[tx]);
    }
    maxx=max(maxx,n-w[x]);
    if(maxx<sum) {
        sum=maxx;
        node=x;
    }
    else if(maxx==sum) {
        node=min(x,node);
    }
}
int main(){
    while(cin>>n) {
        sum=inf;node=0;
        memset(w,0,sizeof w);
        for(int i=1;i<=n;i++) tree[i].clear();

        for(int i=1;i<n;i++) {
            int u,v;
            cin>>u>>v;
            tree[u].push_back(v);
            tree[v].push_back(u);
        }

        dfs(1,0);
        cout<<node<<' '<<sum<<endl;
    }
} 

Rinne Loves Edges

解题思路

坑人的地方就是最后的数据说明：M=N-1，就是棵树！
定义好dp的含义才是最重要的。
dp[i]表示以i为根节点的子树，不存在1度结点与之相连通，所需要的最小花费。
转移方程：dp[x] = ∑(min(dp[tx], cost(x,tx))) 其中tx为x的子节点。

AC代码

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e5+100;
struct node{
    int to,cost;
};
vector<node> g[N];
int dp[N],n,m,s;
void dfs(int x,int fa) {
    int sum=0;
    dp[x]=0;
    for(int i=0;i<g[x].size();i++) {
        if(fa==g[x][i].to) continue;
        dfs(g[x][i].to,x);
        if(dp[g[x][i].to]==0) dp[g[x][i].to]=inf;//注意！
        dp[x]+=min(dp[g[x][i].to],g[x][i].cost);
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++) { 
        int u,v,w;cin>>u>>v>>w;
        node tmp;tmp.to=v;tmp.cost=w;
        //用结构体的思考过程（比较好想）：如何存花费，用二维数组明显开不下，那就用二维vector，虽然能存下了，但是dfs的时候对应儿子结点，最后为了将结点与花费联系起来，就放在了结构体vector里了
        g[u].pb(tmp);
        tmp.to=u;
        g[v].pb(tmp);
    }
    dfs(s,0);
    cout<<dp[s]<<endl;
}