题目地址
牛客B题学到了 __int128的神仙用法
牛客I题 记忆化搜索
//MADE BY Y_is_sunshine; //#include <bits/stdc++.h> //#include <memory.h> #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <sstream> #include <cstdio> #include <vector> #include <string> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define INF 0x3f3f3f3f #define MAXN 20005 const int mod = 1e5 + 7; const double PI = acos(-1); using namespace std; int N, M, K; long long ans = 0; long long dp[MAXN][2020]; vector<pair<int, int> > v[MAXN]; void init(void) { for (int i = 1; i <= N; i++) v[i].clear(); memset(dp, 0, sizeof(dp)); ans = 0; } void dfs(int u, int fa) { for (auto it1 : v[u]) { int v = it1.first; int cost = it1.second; if (it1.first == fa) continue; dfs(it1.first, u); for (int i = 0; i < 2019; i++) { ans += dp[u][(2019 - (i + cost) % 2019) % 2019] * dp[v][i]; } for (int i = 0; i < 2019; i++) { dp[u][(i + cost) % 2019] += dp[v][i]; } } ans += dp[u][0]; dp[u][0]++; } int main(void) { freopen("data.txt", "r", stdin); ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); while (cin >> N) { int a, b, c; ans = 0; for (int i = 1; i <= N; ++i) { v[i].clear(); for (int j = 0; j < 2020; ++j) dp[i][j] = 0; } for (int i = 1; i < N; i++) { cin >> a >> b >> c; v[a].push_back(make_pair(b, c)); v[b].push_back(make_pair(a, c)); } dfs(1, -1); cout << ans << endl; } freopen("CON", "r", stdin); system("pause"); return 0; }