2022 东北四省赛 VP记录/补题

VP情况 ABCDEFGHIJKLM待补ACAC(-6)ACAC补题补题–AC(-2)–ACAC– A.Encryption

–待补–

B.Capital Progra 题目分析

要求在给定的图上选择一个连通块，使得该连通块到其他点的距离和最小。

考虑贪心的选取，我们可以将图展开，然后从叶节点开始按照逆 B F S BFS BFS序进行删点，删完 n − k n-k n−k个为止。可以用拓扑排序实现这个过程，设 d i s [ i ] dis[i] dis[i]表示该点子树的边数(边权和)，在排序过程中更新最大值即可。

Code

#include 
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10;
vector g[N];

int deg[N], dis[N];

inline void solve(){
    int n, k; cin >> n >> k;
    for(int i = 1; i > u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
        deg[u]++, deg[v]++;
    }
    if(n == k){ cout