10203 2024. 03. 29 13:35:08 111 Testvérvárosok cpp17 Elfogadva 100/100 101ms 37932 KiB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,K;
	cin>>N>>K;
	vector<vector<pair<int,int>>>g(N+1);
	for(int i=0;i<N-1;i++){
		int a,b,d;
		cin>>a>>b>>d;
		g[a].emplace_back(b,d);
		g[b].emplace_back(a,d);
	}
	int ans=0;
	auto dfs=[&](auto self,int i,int p,int x)->map<int,int>{
		map<int,int>s;
		for(auto[j,d]:g[i]){
			if(j==p){
				continue;
			}
			auto z=self(self,j,i,x+d);
			ans+=z[x%K];
			if(z.size()>s.size()){
				swap(s,z);
			}
			for(auto[y,c]:z){
				ans+=s[((x*2-y)%K+K)%K]*c;
			}
			for(auto[y,c]:z){
				s[y]+=c;
			}
		}
		s[x%K]++;
		return s;
	};
	dfs(dfs,1,0,0);
	cout<<ans<<'\n';
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1832 KiB
2 Elfogadva 3ms 2068 KiB
subtask2 15/15
3 Elfogadva 3ms 2284 KiB
4 Elfogadva 3ms 2608 KiB
5 Elfogadva 4ms 2924 KiB
6 Elfogadva 4ms 3184 KiB
7 Elfogadva 3ms 2888 KiB
8 Elfogadva 3ms 2992 KiB
9 Elfogadva 4ms 3524 KiB
subtask3 15/15
10 Elfogadva 10ms 4980 KiB
11 Elfogadva 4ms 5000 KiB
12 Elfogadva 37ms 10708 KiB
13 Elfogadva 32ms 10240 KiB
14 Elfogadva 37ms 11260 KiB
subtask4 20/20
15 Elfogadva 3ms 3892 KiB
16 Elfogadva 3ms 4416 KiB
17 Elfogadva 8ms 7584 KiB
18 Elfogadva 20ms 18828 KiB
19 Elfogadva 29ms 25732 KiB
20 Elfogadva 37ms 34000 KiB
21 Elfogadva 29ms 32004 KiB
22 Elfogadva 45ms 37932 KiB
subtask5 50/50
23 Elfogadva 90ms 13504 KiB
24 Elfogadva 52ms 9792 KiB
25 Elfogadva 64ms 10568 KiB
26 Elfogadva 46ms 6820 KiB
27 Elfogadva 48ms 10036 KiB
28 Elfogadva 76ms 12864 KiB
29 Elfogadva 97ms 12900 KiB
30 Elfogadva 32ms 11756 KiB
31 Elfogadva 101ms 13964 KiB