5264 2023. 04. 24 17:42:46 ZsofiaKeresztely Testvérvárosok cpp14 Elfogadva 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1824 KiB
2 Elfogadva 3ms 2236 KiB
subtask2 15/15
3 Elfogadva 3ms 2812 KiB
4 Elfogadva 3ms 2556 KiB
5 Elfogadva 4ms 3448 KiB
6 Elfogadva 13ms 7908 KiB
7 Elfogadva 3ms 3060 KiB
8 Elfogadva 8ms 6228 KiB
9 Elfogadva 4ms 4040 KiB
subtask3 15/15
10 Elfogadva 10ms 6132 KiB
11 Elfogadva 4ms 4372 KiB
12 Elfogadva 37ms 15168 KiB
13 Elfogadva 32ms 15172 KiB
14 Elfogadva 37ms 17404 KiB
subtask4 20/20
15 Elfogadva 4ms 7440 KiB
16 Elfogadva 17ms 14148 KiB
17 Elfogadva 48ms 30300 KiB
18 Elfogadva 172ms 98008 KiB
19 Elfogadva 131ms 73204 KiB
20 Elfogadva 108ms 65676 KiB
21 Elfogadva 28ms 25632 KiB
22 Elfogadva 689ms 358388 KiB
subtask5 50/50
23 Elfogadva 537ms 266564 KiB
24 Elfogadva 312ms 160544 KiB
25 Elfogadva 317ms 161560 KiB
26 Elfogadva 126ms 72532 KiB
27 Elfogadva 203ms 113304 KiB
28 Elfogadva 185ms 97500 KiB
29 Elfogadva 703ms 355580 KiB
30 Elfogadva 34ms 24444 KiB
31 Elfogadva 588ms 314312 KiB