Back to Leetcode

Readme

Binary_Search/3559.Number-of-Ways-to-Assign-Edge-Weights-II/Readme.md

latest771 B
Original Source

3559.Number-of-Ways-to-Assign-Edge-Weights-II

我们很容易看出,可以用binary lifting高效地求出任意两点之间的edge的个数d。显然,每段edge可以赋值1或者2,因此总共会有2^d种组合。其中有多少种方法能使得总路径长度恰好是奇数呢?结论很简单,就是它们的一半,即2^(d-1)种。

我们可以用动态规划来推论一下。dp1[i]表示i条边组成的总长度为奇数的组合数,dp2[i]表示i条边组成的总长度为偶数的组合数。我们的转移方程是

dp1[i] = dp2[i-1]+dp1[i-1];
dp2[i] = dp1[i-1]+dp2[i-1];

初始条件是dp1[1]=dp2[1]=1,显然会有对任意的i,都有dp1[i]=dp2[i]。故i条边组成的总长度为偶数和奇数的组合数一定相等。