链接
https://nanti.jisuanke.com/t/39262
题解
f
i
j
f_{ij}
fij表示
i
i
i号点颜色为
j
j
j，整棵子树合法的方案数 暴力就是枚举当前点和儿子节点的颜色 他有个条件说边权两两不同，可以发现在
m
∗
m
m*m
m∗m的
g
c
d
gcd
gcd矩阵中，每个位置上都对应一个转移 而且每个转移肯定都能对应到矩阵中的某个位置 综上所述，有效的转移只有
O
(
m
2
)
O(m^2)
O(m2)个 总的复杂度也就降到
O
(
n
m
+
m
2
)
O(nm+m^2)
O(nm+m2)
代码
#include<bits/stdc++.h>
#define maxn 1010
#define linf (1ll<<60)
#define iinf 0x3f3f3f3f
#define eps 1e-8
#define cl(x) memset(x,0,sizeof(x))
#define mod 1000000007ll
using namespace std
;
typedef long long ll
;
ll
read(ll x
=0)
{
int c
, f
=1;
for(c
=getchar();!isdigit(c
);c
=getchar())if(c
=='-')f
=-f
;
for(;isdigit(c
);c
=getchar())x
=x
*10+c
-48;
return f
*x
;
}
ll N
, M
, head
[maxn
], to
[maxn
], nex
[maxn
], d
[maxn
], etot
, w
[maxn
], f
[maxn
][60], g
[maxn
];
vector
<ll
> tran
[maxn
][maxn
];
set
<ll
> val
;
void adde(ll a
, ll b
, ll c
){to
[++etot
]=b
;w
[etot
]=c
;nex
[etot
]=head
[a
];head
[a
]=etot
;}
ll
gcd(ll a
, ll b
){return !b
?a
:gcd(b
,a
%b
);}
void dfs(ll pos
, ll pre
)
{
ll s
;
for(auto p
=head
[pos
];p
;p
=nex
[p
])
if(to
[p
]!=pre
)
{
dfs(to
[p
],pos
);
}
for(auto c
=1;c
<=M
;c
++)
{
g
[pos
] += f
[pos
][c
];
g
[pos
] %= mod
;
f
[pos
][c
]=1;
for(auto p
=head
[pos
];p
;p
=nex
[p
])
{
if(to
[p
]==pre
)continue;
s
=g
[to
[p
]];
for(auto son
:tran
[c
][w
[p
]])
{
s
-=f
[to
[p
]][son
];
}
f
[pos
][c
] *= s
%mod
;
f
[pos
][c
] %= mod
;
}
g
[pos
] += f
[pos
][c
];
g
[pos
] %= mod
;
}
}
int main()
{
ll a
, b
, c
, i
, j
, ans(0);
N
=read(), M
=read();
for(i
=1;i
<N
;i
++)
{
a
=read(), b
=read(), c
=read();
adde(a
,b
,c
), adde(b
,a
,c
);
val
.emplace(c
);
}
for(i
=1;i
<=M
;i
++)for(j
=1;j
<=M
;j
++)
{
if( val
.find(__gcd(i
,j
)) != val
.end() )
{
tran
[i
][__gcd(i
,j
)].emplace_back(j
);
}
}
dfs(1,0);
for(i
=1;i
<=M
;i
++)
{
ans
=(ans
+f
[1][i
])%mod
;
}
cout
<<(ans
+mod
)%mod
<<endl
;
return 0;
}
