hdu 4705 Y (계수)

3976 단어
제목 링크: hdu 4705 Y

코드

#pragma comment(linker, "/STACK:16777216") 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
typedef unsigned long long ll;
const int maxn = 1e5 + 5;

ll ans;
int N, sz[maxn];
vector<int> G[maxn];

void init () {
    for (int i = 1; i <= N; i++) G[i].clear();

    int u, v;
    for (int i = 1; i < N; i++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    ans = 0;
}

void dfs (int u, int f) {
    sz[u] = 0;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == f) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }

    int nd = sz[u], fz = N-1-sz[u];
    ll sum = 1LL * fz * nd;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == f) continue;
        nd -= sz[v];
        sum += 1LL * sz[v] * nd;
    }

    ans += 1LL * fz * (sum - 1LL * fz * (N-1-fz));
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == f) continue;
        ans += 1LL * sz[v] * (sum - 1LL * sz[v] * (N-1-sz[v]));
    }

    sz[u]++;
}

int main () {
    while (scanf("%d", &N) == 1) {
        init();
        dfs(1, 0);
        printf("%I64u
", ans / 3);
    }
    return 0;
}
[Vision Transformer] 코드 설명
[TIL] 첫 번째 장고 앱 작성하기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage