10202 2024. 03. 29 13:32:51 111 Testvérvárosok cpp17 Időlimit túllépés 15/100 1.582s 43696 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)->multiset<int>{
		multiset<int>s;
		for(auto[j,d]:g[i]){
			if(j==p){
				continue;
			}
			auto z=self(self,j,i,x+d);
			ans+=z.count(x%K);
			if(z.size()>s.size()){
				swap(s,z);
			}
			for(int y:z){
				ans+=s.count(((x*2-y)%K+K)%K);
			}
			s.insert(z.begin(),z.end());
		}
		s.insert(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 1824 KiB
2 Elfogadva 3ms 2072 KiB
subtask2 15/15
3 Elfogadva 3ms 2284 KiB
4 Elfogadva 3ms 2440 KiB
5 Elfogadva 3ms 2768 KiB
6 Elfogadva 3ms 2768 KiB
7 Elfogadva 4ms 2892 KiB
8 Elfogadva 3ms 2852 KiB
9 Elfogadva 4ms 3140 KiB
subtask3 0/15
10 Elfogadva 363ms 6768 KiB
11 Elfogadva 24ms 5580 KiB
12 Időlimit túllépés 1.582s 8432 KiB
13 Időlimit túllépés 1.582s 7468 KiB
14 Időlimit túllépés 1.562s 7844 KiB
subtask4 0/20
15 Elfogadva 3ms 3508 KiB
16 Elfogadva 3ms 4152 KiB
17 Elfogadva 8ms 8216 KiB
18 Elfogadva 37ms 21764 KiB
19 Elfogadva 82ms 29640 KiB
20 Elfogadva 225ms 39440 KiB
21 Időlimit túllépés 1.577s 18580 KiB
22 Elfogadva 97ms 43696 KiB
subtask5 0/50
23 Elfogadva 100ms 16096 KiB
24 Elfogadva 50ms 10660 KiB
25 Elfogadva 68ms 13364 KiB
26 Elfogadva 23ms 6540 KiB
27 Elfogadva 50ms 10536 KiB
28 Elfogadva 134ms 17032 KiB
29 Elfogadva 96ms 16232 KiB
30 Időlimit túllépés 1.552s 8700 KiB
31 Elfogadva 108ms 17560 KiB