Readme

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条边组成的总长度为偶数和奇数的组合数一定相等。