一道树形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; }