Code

unicornshjl · 2025-04-08 15:41:57 · 个人记录

#include<iostream>
#include<cmath>
#include<cstdio>
#include<random>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<utility>
#include<unordered_map>
#include<unordered_set>
#include<bitset> 
#define int long long
using namespace std;
constexpr int maxn = 1e6 + 10;
constexpr int maxm = 500 + 10;
constexpr int mod = 998244353;
constexpr int mod1 = 1e9 + 7;
constexpr int inf = 1e18 + 10;
constexpr int dx[] = { 1,-1,0,0 };
constexpr int dy[] = { 0,0,1,-1 };
int n, dis[maxn], dis1[maxn], dis2[maxn], n1, n2, maxd, num[maxn], sum[maxn];
vector<int> edge[maxn];
void dfs(int u, int fa) {
    dis[u] = dis[fa] + 1;
    for (auto v : edge[u]) {
        if (v == fa) continue;
        dfs(v, u);
    }
}
void doit1() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dis[0] = -1;
    dfs(1, 0);
    int p = 0;
    for (int i = 1; i <= n; i++)
        if (dis[i] > dis[p])
            p = i;
    int x = p;
    dfs(x, 0);
    for (int i = 1; i <= n; i++) dis1[i] = dis[i];
    p = 0;
    for (int i = 1; i <= n; i++)
        if (dis[i] > dis[p])
            p = i;
    maxd = max(maxd, dis[p]);
    dfs(p, 0);
    for (int i = 1; i <= n; i++) dis1[i] = max(dis1[i], dis[i]);
}
void doit2() {
    cin >> n;
    for (int i = 1; i <= n; i++) edge[i].clear();
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dis[0] = -1;
    dfs(1, 0);
    int p = 0;
    for (int i = 1; i <= n; i++)
        if (dis[i] > dis[p])
            p = i;
    int x = p;
    dfs(x, 0);
    for (int i = 1; i <= n; i++) dis2[i] = dis[i];
    p = 0;
    for (int i = 1; i <= n; i++)
        if (dis[i] > dis[p])
            p = i;
    maxd = max(maxd, dis[p]);
    dfs(p, 0);
    for (int i = 1; i <= n; i++) dis2[i] = max(dis2[i], dis[i]);
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    doit1(); n1 = n;
    doit2(); n2 = n;
    int ans = 0;
    for (int i = 1; i <= n2; i++)
        num[dis2[i]]++, sum[dis2[i]] += dis2[i];
    for (int i = n2; i >= 0; i--)
        num[i] += num[i + 1], sum[i] += sum[i + 1];
    for (int i = 1; i <= n1; i++) {
        int now = max(0ll, maxd - dis1[i] - 1);
        int cur = num[now];
        ans += sum[now] + cur + cur * dis1[i];
        ans += (n2 - cur) * maxd;
    }
    cout << ans << "\n";
    return 0;
}

#include<iostream>
#include<cmath>
#include<cstdio>
#include<random>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<utility>
#include<unordered_map>
#include<unordered_set>
#include<bitset> 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
constexpr int maxn = 2e5 + 10;
constexpr int maxm = 100 + 10;
constexpr int intinf = 1e9 + 10;
constexpr int mod = 998244353;
constexpr ll inf = 1e15 + 10;
constexpr int dx[] = { 1,-1,0,0 };
constexpr int dy[] = { 0,0,1,-1 };
constexpr ld eps = 1e-12;
using namespace std;

ll n, num[maxn], cnt, siz[maxn], g[maxn], dis[maxn], sum, p;
vector<pair<ll, ll>> edge[maxn];

void add(int u, int v, ll w) {
    edge[u].push_back({ v,w });
}

void find(int u, int fa) {
    siz[u] = num[u];
    bool flag = true;
    for (auto [v, w] : edge[u]) {
        if (v == fa) continue;
        find(v, u);
        if (siz[v] > p / 2) flag = false;
        siz[u] += siz[v];
    }
    if (flag && p - siz[u] <= p / 2)
        g[++sum] = u;
}

void dfs(int u, int fa) {
    for (auto [v, w] : edge[u]) {
        if (v == fa) continue;
        dis[v] = dis[u] + w;
        dfs(v, u);
    }
}

void init() {
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> num[i], p += num[i];
    for (int i = 1; i < n; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    find(1, 0);
    ll ans = inf;
    for (int i = 1; i <= sum; i++) {
        for (int i = 1; i <= n; i++) dis[i] = 0;
        dfs(g[i], 0);
        ll res = 0;
        for (int i = 1; i <= n; i++)
            res += num[i] * dis[i];
        ans = min(ans, res);
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    init();
    return 0;
}

#include<iostream>
#include<cmath>
#include<cstdio>
#include<random>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<utility>
#include<unordered_map>
#include<unordered_set>
#include<bitset> 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
constexpr int maxn = 2e5 + 10;
constexpr int maxm = 100 + 10;
constexpr int intinf = 1e9 + 10;
constexpr int mod = 998244353;
constexpr ll inf = 1e15 + 10;
constexpr int dx[] = { 1,-1,0,0 };
constexpr int dy[] = { 0,0,1,-1 };
constexpr ld eps = 1e-12;
using namespace std;

ll n, num[maxn], cnt, g[maxn], dis[maxn], sum, siz[maxn], ans;
vector<int> edge[maxn];

void add(int u, int v) {
    edge[u].push_back(v);
}

void find(int u, int fa) {
    siz[u] = 1;
    bool flag = true;
    for (auto v : edge[u]) {
        if (v == fa) continue;
        find(v, u);
        if (siz[v] > n / 2) flag = false;
        siz[u] += siz[v];
    }
    if (flag && n - siz[u] <= n / 2)
        g[++sum] = u;
}

void init() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        edge[i].clear();
    for (int i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
}

void dfs(int u, int fa) {
    bool flag = false;
    for (auto v : edge[u]) {
        if (v == fa) continue;
        dfs(v, u); flag = true;
    }
    if (flag == false) {
        ans = u;
    }
}

void solve() {
    sum = 0;
    find(1, 0);
    if (sum == 1) {
        for (auto v : edge[g[1]]) {
            cout << g[1] << " " << v << "\n";
            cout << g[1] << " " << v << "\n";
            return;
        }
    }
    dfs(g[1], g[2]);
    for (auto v : edge[ans]) {
        cout << ans << " " << v << "\n";
        cout << ans << " " << g[2] << "\n";
        return;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        init();
        solve();
    }
    return 0;
}