「KFCOI Round #1」遥不可及 菊花部分分

koukilee · 2024-12-14 10:01:02 · 个人记录

/* The code is from koukilee*/
#include <bits/stdc++.h>

using i32 = int; using i64 = long long;
constexpr i64 MAXN = 1010100, mod = 1e9 + 7, INF = 992009100720100812; 

//static char buf[1000000], *p1 = buf, *p2 = buf, obuf[1000000], *p3 = obuf; 
//#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++
//#define putchar(x) (p3 - obuf < 1000000) ? (*p3++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3++ = x)
inline void read (i64 &sum) noexcept {
    i64 tf = 0; char ch = getchar(); sum = 0;
    while (ch < '0' || ch > '9') tf = ch == '-' ? 1 : 0, ch = getchar();
    while (ch >= '0' && ch <= '9') sum = (sum << 1) + (sum << 3) + (ch ^ 48), ch = getchar();
    (tf) && (sum =- sum);
}template <typename i64,typename ...Args>
inline void read (i64 &tmp, Args &...tmps) noexcept{read(tmp); read(tmps...);}
void printt (i64 x) noexcept {if(x >= 10) printt(x / 10); putchar(x % 10 + '0');} 
inline void print (i64 x) noexcept{x < 0 ? putchar('-'), printt(-x) : printt(x);}
inline void put (i64 x) noexcept{print(x), putchar('\n');}

i64 n, du[MAXN], root, maxa, maxb, lena, lenb, ans;
std::vector <std::pair <i64, i64> > G[MAXN];

int main() noexcept{
    read (n);

    for (i32 i = 1; i < n; i++){
        i64 x, y, z; read (x, y, z);
        G[x].push_back ({y, z}), G[y].push_back ({x, z});
        du[x]++, du[y]++;
    }

    for (i32 i = 1; i <= n; i++)
        if (du[i] == n - 1) {
            root = i; break;
        }

    for (auto it : G[root]){
        if (it.second >= maxa) {
            if (it.second == maxa)
                lena++;
            else
                maxb = maxa, lenb = lena, maxa = it.second, lena = 1;
        } else if (it.second > maxb)
            maxb = it.second, lenb = 1;
        else if (it.second == maxb)
            lenb++;
    }

    ans = lena << 1;

    for (auto it : G[root]) {
        if (it.second == maxa) {
            if (lena == 1) ans += lenb * 3;
            else ans += (lena - 1) * 3;
        } else ans += lena * 3;
    }

    put (ans);
    //fwrite(obuf,p3-obuf,1,stdout);
    return 0;
}