5264 2023. 04. 24 17:42:46 ZsofiaKeresztely Testvérvárosok cpp14 Accepted 100/100 703ms 358388 KiB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define se second
#define fi first
vector<vector<pii> > g;
vector<vector<int> > ls;
int n, k;

int dfs(int p, int v){
    int r = 0;
    ls[v][0] = 1;
    for (pii x : g[v]){
        if (x.fi == p) continue;
        r += dfs(v, x.fi);
        for (int i=0; i<k; i++){
            ls[v][(i+x.se)%k] += ls[x.fi][i];
        }
    }
    r *= 2;
    for (pii x : g[v]){
        if (x.fi == p) continue;
        for (int i=0; i<k; i++){
            r += (ls[v][i] - ls[x.fi][(i-x.se+500*k)%k]) * ls[x.fi][(501*k-i-x.se)%k];
        }
    }
    r += ls[v][0] - 1;
    return r/2;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    g.resize(n+1);
    ls.assign(n+1, vector<int> (k, 0));
    for (int i=0; i<n-1; i++){
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    cout << dfs(0, 1);
    return 0;
}
Subtask Sum Test Verdict Time Memory
subtask1 0/0
1 Accepted 3ms 1824 KiB
2 Accepted 3ms 2236 KiB
subtask2 15/15
3 Accepted 3ms 2812 KiB
4 Accepted 3ms 2556 KiB
5 Accepted 4ms 3448 KiB
6 Accepted 13ms 7908 KiB
7 Accepted 3ms 3060 KiB
8 Accepted 8ms 6228 KiB
9 Accepted 4ms 4040 KiB
subtask3 15/15
10 Accepted 10ms 6132 KiB
11 Accepted 4ms 4372 KiB
12 Accepted 37ms 15168 KiB
13 Accepted 32ms 15172 KiB
14 Accepted 37ms 17404 KiB
subtask4 20/20
15 Accepted 4ms 7440 KiB
16 Accepted 17ms 14148 KiB
17 Accepted 48ms 30300 KiB
18 Accepted 172ms 98008 KiB
19 Accepted 131ms 73204 KiB
20 Accepted 108ms 65676 KiB
21 Accepted 28ms 25632 KiB
22 Accepted 689ms 358388 KiB
subtask5 50/50
23 Accepted 537ms 266564 KiB
24 Accepted 312ms 160544 KiB
25 Accepted 317ms 161560 KiB
26 Accepted 126ms 72532 KiB
27 Accepted 203ms 113304 KiB
28 Accepted 185ms 97500 KiB
29 Accepted 703ms 355580 KiB
30 Accepted 34ms 24444 KiB
31 Accepted 588ms 314312 KiB