2019

一道树形dp或者是点分治。点分治常数更下，但是我这种菜鸡当然树形dp啦。

因为有取模操作的存在，所以我们复杂度比较低。

我们让 dp[x][j] 表示距离x节点，mod 2019 之后的值为j的种数。

然后就可以转移啦，转移公式不难，自己应该能推出来。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e4+10;
int n,dp[N][2100],res;
int head[N],nex[N<<1],to[N<<1],w[N<<1],tot;
inline void add(int a,int b,int c){
	to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void init(){
	memset(head,0,sizeof head); tot=res=0;
	for(int i=1;i<=n;i++)	memset(dp[i],0,sizeof dp[i]);
}
void dfs(int x,int fa){
	dp[x][0]=1;
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa)	continue;
		dfs(to[i],x);
		for(int j=0;j<2019;j++)	
			res+=dp[x][j]*dp[to[i]][(2019-j-w[i]+2019)%2019];
		for(int j=0;j<2019;j++)
			if(j>=w[i])	dp[x][j]+=dp[to[i]][j-w[i]];
			else	dp[x][j]+=dp[to[i]][2019+j-w[i]];
	}
}
signed main(){
	while(cin>>n){
		init();
		for(int i=1;i<n;i++){
			int a,b,c;	scanf("%lld %lld %lld",&a,&b,&c);
			add(a,b,c);	add(b,a,c);
		}
		dfs(1,0);
		cout<<res<<endl;
	}
	return 0;
}