AlgorithmAndLeetCode · pull · Jun 27, 2025 · Jun 27, 2025 · Jun 27, 2025 · Jun 27, 2025
diff --git a/...umber-of-Ways-to-Assign-Edge-Weights-II/3559.Number-of-Ways-to-Assign-Edge-Weights-II.cpp b/...umber-of-Ways-to-Assign-Edge-Weights-II/3559.Number-of-Ways-to-Assign-Edge-Weights-II.cpp
@@ -0,0 +1,93 @@
+using ll = long long;
+const int MAXN = 100005;
+const int LOGN = 17;
+class Solution {
+public:
+    vector<pair<int,int>> adj[MAXN];
+    int up[MAXN][LOGN+1];
+    int depth[MAXN];
+    ll distRoot[MAXN];
+
+    void dfs(int cur, int parent)
+    {
+        up[cur][0] = parent;
+        for(auto &[v,w]: adj[cur])
+        {
+            if(v == parent) continue;
+            depth[v] = depth[cur] + 1;
+            distRoot[v] = distRoot[cur] + w;
+            dfs(v, cur);
+        }
+    }
+
+    int lca(int a, int b)
+    {
+        if(depth[a] < depth[b]) swap(a,b);
+        int diff = depth[a] - depth[b];
+        for(int k = 0; k <= LOGN; k++){
+            if(diff & (1<<k)) a = up[a][k];
+        }
+        if(a == b) return a;
+        for(int k = LOGN; k >= 0; k--){
+            if(up[a][k] != up[b][k]){
+                a = up[a][k];
+                b = up[b][k];
+            }
+        }
+        return up[a][0];
+    }
+
+    ll dist(int a, int b)
+    {
+        int c = lca(a,b);
+        return distRoot[a] + distRoot[b] - 2*distRoot[c];
+    }
+
+    ll stepUp(int u, int k) {        
+        for (int i=LOGN; i>=0; i--) {
+            if ((k>>i)&1) {
+                u = up[u][i];
+            }
+        }
+        return u;
+    }
+
+    vector<int> assignEdgeWeights(vector<vector<int>>& edges, vector<vector<int>>& queries) {
+        int n = edges.size()+1;
+
+        for (auto& edge: edges)
+        {
+            int u = edge[0], v = edge[1], w = 1;
+            adj[u].push_back({v,w});
+            adj[v].push_back({u,w});
+        }
+
+        depth[1] = 0;
+        distRoot[1] = 0;
+        dfs(1, 1);
+
+        for(int k = 1; k <= LOGN; k++) {
+            for(int v = 1; v <= n; v++) {
+                up[v][k] = up[up[v][k-1]][k-1];
+            }
+        }
+
+        vector<ll>power(n+1);
+        ll M = 1e9+7;
+        power[0] = 1;
+        for (int i=1; i<=n; i++)
+            power[i] = power[i-1]*2%M;
+
+        vector<int>rets;
+        for (auto&q: queries) {
+            int u = q[0], v = q[1];
+            int d = dist(u,v);            
+            if (d==0)
+                rets.push_back(0);
+            else
+                rets.push_back(power[d-1]);
+        }
+
+        return rets;
+    }
+};
diff --git a/Binary_Search/3559.Number-of-Ways-to-Assign-Edge-Weights-II/Readme.md b/Binary_Search/3559.Number-of-Ways-to-Assign-Edge-Weights-II/Readme.md
@@ -0,0 +1,10 @@
+### 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];
+dp2[i] = dp1[i-1];
+```
+初始条件是`dp1[1]=dp2[1]=1`，显然会有对任意的i，都有`dp1[i]=dp2[i]`。故i条边组成的总长度为偶数和奇数的组合数一定相等。
diff --git a/Readme.md b/Readme.md
@@ -110,6 +110,7 @@
 [2851.String-Transformation](https://github.com/wisdompeak/LeetCode/tree/master/Dynamic_Programming/2851.String-Transformation) (H+)      
 [3534.Path-Existence-Queries-in-a-Graph-II](https://github.com/wisdompeak/LeetCode/tree/master/Binary_Search/3534.Path-Existence-Queries-in-a-Graph-II) (H)      
 [3553.Minimum-Weighted-Subgraph-With-the-Required-Paths-II](https://github.com/wisdompeak/LeetCode/tree/master/Binary_Search/3553.Minimum-Weighted-Subgraph-With-the-Required-Paths-II) (H)      
+[3559.Number-of-Ways-to-Assign-Edge-Weights-II](https://github.com/wisdompeak/LeetCode/tree/master/Binary_Search/3559.Number-of-Ways-to-Assign-Edge-Weights-II) (H-)      
 [3585.Find-Weighted-Median-Node-in-Tree](https://github.com/wisdompeak/LeetCode/tree/master/Binary_Search/3585.Find-Weighted-Median-Node-in-Tree) (H)      
 * ``Binary Search by Value``  
 [410.Split-Array-Largest-Sum](https://github.com/wisdompeak/LeetCode/tree/master/Dynamic_Programming/410.Split-Array-Largest-Sum) (H-)