2026-05-04：樹組的交互代價總和。用go語言，給定一個整數(shù) n，以及一棵有 n 個節(jié)點(diǎn)的無向樹，節(jié)點(diǎn)編號為 0 到 n-1。樹的結(jié)構(gòu)由數(shù)組 edges

2026-05-04 00:09:38　來源: moonfdd

北京舉報

分享至

2026-05-04：樹組的交互代價總和。用go語言，給定一個整數(shù) n，以及一棵有 n 個節(jié)點(diǎn)的無向樹，節(jié)點(diǎn)編號為 0 到 n-1。樹的結(jié)構(gòu)由數(shù)組 edges 表示：數(shù)組長度為 n-1，其中 edges[i] = [u, v] 表示節(jié)點(diǎn) u 與節(jié)點(diǎn) v 之間有一條無向邊。

另給定一個數(shù)組 group，長度為 n。group[i] 表示節(jié)點(diǎn) i 所屬的組。

如果兩個節(jié)點(diǎn) u 和 v 滿足 group[u] == group[v]，則稱它們屬于同一組。由于是樹結(jié)構(gòu)，任意兩個節(jié)點(diǎn)之間都存在且僅存在一條唯一路徑。所謂交互代價定義為：這條唯一路徑上包含的邊的數(shù)量。

目標(biāo)：枚舉所有無序且不同的節(jié)點(diǎn)對 (u, v)，要求它們同組（group[u] == group[v]）。把這些節(jié)點(diǎn)對的交互代價全部累加并返回總和；若不存在滿足條件的節(jié)點(diǎn)對，則返回 0。

1 <= n <= 100000。

edges.length == n - 1。

edges[i] = [ui, vi]。

0 <= ui, vi <= n - 1。

group.length == n。

1 <= group[i] <= 20。

輸入保證 edges 表示一棵有效的樹。

輸入： n = 3, edges = [[0,1],[1,2]], group = [3,2,3]。

輸出： 2。

解釋：

節(jié)點(diǎn) 0 和節(jié)點(diǎn) 2 屬于組 3，它們之間的交互代價為 2。

節(jié)點(diǎn) 1 屬于不同的組，因此沒有有效的節(jié)點(diǎn)對。

總交互代價為 2。

題目來自力扣3786。

代碼執(zhí)行全流程詳細(xì)拆解第一步：構(gòu)建原始樹的鄰接表

1. 初始化一個長度為n的二維數(shù)組，作為無向樹的鄰接表；
2. 遍歷所有邊，把每條邊的兩個節(jié)點(diǎn)互相添加到對方的鄰接列表中；
3. 作用：讓程序可以快速訪問每個節(jié)點(diǎn)的所有相鄰節(jié)點(diǎn)，為后續(xù)樹的遍歷做準(zhǔn)備。

第二步：預(yù)處理樹的基礎(chǔ)信息（DFS + 倍增LCA）

這一步是為了快速求任意兩點(diǎn)的最近公共祖先（LCA）和兩點(diǎn)間路徑長度，是樹問題的核心預(yù)處理。

子步驟1：DFS遍歷樹，記錄核心信息

1. 定義遞歸函數(shù)，從根節(jié)點(diǎn)0開始遍歷整棵樹；
2. 記錄每個節(jié)點(diǎn)的DFS時間戳（dfn）：用于后續(xù)給節(jié)點(diǎn)排序，是構(gòu)建虛樹的關(guān)鍵；
3. 記錄每個節(jié)點(diǎn)的父節(jié)點(diǎn)（第一層祖先）；
4. 記錄每個節(jié)點(diǎn)的深度（dep）：根節(jié)點(diǎn)深度為0，子節(jié)點(diǎn)深度=父節(jié)點(diǎn)+1；
5. 深度的作用：兩點(diǎn)間路徑邊數(shù) =深度[u] + 深度[v] - 2×深度[LCA(u,v)]。

子步驟2：倍增法預(yù)處理祖先數(shù)組

1. 計(jì)算樹的最大深度對應(yīng)的二進(jìn)制位數(shù)，確定倍增的層數(shù)；
2. 預(yù)處理每個節(jié)點(diǎn)的2^i級祖先（2級、4級、8級...祖先）；
3. 作用：實(shí)現(xiàn)O(logn)時間查詢?nèi)我鈨蓚€節(jié)點(diǎn)的最近公共祖先（LCA）。

子步驟3：封裝LCA查詢函數(shù)

1. 封裝兩個工具函數(shù)：

? 把節(jié)點(diǎn)向上提升到指定深度；
? 求任意兩個節(jié)點(diǎn)的最近公共祖先；

2. 這是后續(xù)計(jì)算路徑長度、構(gòu)建虛樹的基礎(chǔ)工具。

第三步：按分組歸類所有節(jié)點(diǎn)

1. 創(chuàng)建一個哈希表（字典），key=組號，value=該組所有節(jié)點(diǎn)的列表；
2. 遍歷所有節(jié)點(diǎn)，把每個節(jié)點(diǎn)按照group數(shù)組的值，放入對應(yīng)組的列表中；
3. 作用：后續(xù)只需要逐組計(jì)算，組號最多20個，極大減少計(jì)算量。

第四步：對每一組單獨(dú)構(gòu)建「虛樹」（核心優(yōu)化）

因?yàn)榻M號只有20個，我們逐個組處理，每組獨(dú)立計(jì)算貢獻(xiàn)：

虛樹作用：只保留當(dāng)前組的節(jié)點(diǎn) + 這些節(jié)點(diǎn)之間路徑的必要公共祖先，剔除無關(guān)節(jié)點(diǎn)，把大樹壓縮成小樹，大幅降低計(jì)算量。

單組構(gòu)建虛樹的完整步驟

1.按DFS時間戳排序：把當(dāng)前組的所有節(jié)點(diǎn)，按照第一步記錄的dfn從小到大排序；
2.初始化棧和虛樹：用根節(jié)點(diǎn)作為棧的初始元素，清空虛樹結(jié)構(gòu)；
3.標(biāo)記關(guān)鍵節(jié)點(diǎn)：把當(dāng)前組的節(jié)點(diǎn)標(biāo)記為「真實(shí)關(guān)鍵節(jié)點(diǎn)」；
4.棧+LCA構(gòu)建虛樹：

? 遍歷排序后的每個節(jié)點(diǎn)；
? 計(jì)算棧頂節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的LCA（路徑拐點(diǎn)）；
? 不斷回溯棧，給虛樹添加邊，直到棧頂深度小于LCA深度；
? 如果LCA不在棧中，將其加入棧和虛樹；
? 最后把當(dāng)前節(jié)點(diǎn)入棧；

5.收尾加邊：遍歷結(jié)束后，把棧中剩余節(jié)點(diǎn)依次連邊，完成虛樹構(gòu)建。

第五步：在虛樹上DFS計(jì)算本組的交互代價（貢獻(xiàn)法）

這是計(jì)算答案的核心步驟，使用貢獻(xiàn)法：不枚舉所有節(jié)點(diǎn)對（會超時），而是計(jì)算每條邊被多少對節(jié)點(diǎn)經(jīng)過，總代價 = 邊數(shù) × 經(jīng)過的節(jié)點(diǎn)對數(shù)。

計(jì)算步驟

1. 定義遞歸DFS函數(shù)，遍歷當(dāng)前組的虛樹；
2. 遞歸統(tǒng)計(jì)每個子樹中當(dāng)前組的節(jié)點(diǎn)數(shù)量；
3. 對于虛樹上的每一條邊：

? 邊的實(shí)際長度 = 子節(jié)點(diǎn)深度 - 父節(jié)點(diǎn)深度（對應(yīng)原始樹的邊數(shù)）；
? 設(shè)子樹內(nèi)有sz個本組節(jié)點(diǎn)，本組總節(jié)點(diǎn)數(shù)為total；
? 這條邊會被sz × (total - sz)對節(jié)點(diǎn)經(jīng)過；
? 本組總代價 += 邊長度 ×sz × (total - sz)；

4. 把本組的代價累加到全局答案中；

5. 一組計(jì)算完成后，重置虛樹，開始處理下一組。

第六步：所有組計(jì)算完成，返回最終答案

1. 遍歷完所有組（最多20組）；
2. 全局累加的結(jié)果就是所有同組節(jié)點(diǎn)對的交互代價總和；
3. 示例中僅組3貢獻(xiàn)了2，最終輸出2。

時間復(fù)雜度 & 額外空間復(fù)雜度分析一、總時間復(fù)雜度

O(n × logn + G × k × logk)
拆解說明：

1.預(yù)處理LCA：DFS遍歷樹是O(n)，倍增預(yù)處理是O(n × logn)；
2.分組歸類：O(n)；
3.構(gòu)建虛樹+計(jì)算貢獻(xiàn)：

? 組數(shù)量G ≤ 20（題目限定）；
? 每組節(jié)點(diǎn)數(shù)k，排序O(k logk)，構(gòu)建虛樹+DFSO(k)；
? 所有組總耗時O(n logn)；

4. 整體主導(dǎo)項(xiàng)：O(n × logn)，完全滿足n=1e5的時間要求。

二、總額外空間復(fù)雜度

O(n × logn)
拆解說明：

1. 鄰接表：O(n)；
2. 倍增祖先數(shù)組：O(n × 17)（log?(1e5)≈17），是核心空間開銷；
3. DFN、深度數(shù)組、虛樹、棧、哈希表：均為O(n)；
4. 整體空間復(fù)雜度由倍增數(shù)組主導(dǎo)：O(n × logn)。

總結(jié)

1. 整體流程：建原始樹 → 預(yù)處理LCA → 按組分節(jié)點(diǎn) → 每組建虛樹壓縮 → 貢獻(xiàn)法算代價 → 累加答案；
2. 核心優(yōu)化：利用group[i]≤20的限定，逐組處理+虛樹壓縮，避免暴力枚舉節(jié)點(diǎn)對；
3. 時間復(fù)雜度：O(n logn)，高效處理1e5節(jié)點(diǎn)；
4. 空間復(fù)雜度：O(n logn)，符合算法題常規(guī)空間要求。

Go完整代碼如下：

package main

 import (
    "fmt"
    "math/bits"
    "slices"
)

 func interactionCosts(n int, edges [][]int, group []int) (ans int64) {
    g := make([][]int, n)
    for _, e := range edges {
        v, w := e[0], e[1]
        g[v] = append(g[v], w)
        g[w] = append(g[w], v)
    }

     dfn := make([]int, n)
    ts := 0
    pa := make([][17]int, n)
    dep := make([]int, n)
    var build func(int, int)
    build = func(v, p int) {
        dfn[v] = ts
        ts++
        pa[v][0] = p
        for _, w := range g[v] {
            if w != p {
                dep[w] = dep[v] + 1
                build(w, v)
            }
        }
    }
    build(0, -1)
    mx := bits.Len(uint(n))
    for i := range mx - 1 {
        for v := range pa {
            p := pa[v][i]
            if p != -1 {
                pa[v][i+1] = pa[p][i]
            } else {
                pa[v][i+1] = -1
            }
        }
    }
    uptoDep := func(v, d int)int {
        for k := uint32(dep[v] - d); k > 0; k &= k - 1 {
            v = pa[v][bits.TrailingZeros32(k)]
        }
        return v
    }
    getLCA := func(v, w int)int {
        if dep[v] > dep[w] {
            v, w = w, v
        }
        w = uptoDep(w, dep[v])
        if w == v {
            return v
        }
        for i := mx - 1; i >= 0; i-- {
            pv, pw := pa[v][i], pa[w][i]
            if pv != pw {
                v, w = pv, pw
            }
        }
        return pa[v][0]
    }

     nodesMap := map[int][]int{}
    for i, x := range group {
        nodesMap[x] = append(nodesMap[x], i)
    }

     vt := make([][]int, n)   // 虛樹
    isNode := make([]int, n) // 用來區(qū)分是關(guān)鍵節(jié)點(diǎn)還是 LCA
    for i := range isNode {
        isNode[i] = -1
    }
    addVtEdge := func(v, w int) {
        vt[v] = append(vt[v], w) // 往虛樹上添加一條有向邊
    }
    const root = 0
    st := []int{root} // 用根節(jié)點(diǎn)作為棧底哨兵

     for val, nodes := range nodesMap {
        // 對于相同點(diǎn)權(quán)的這一組關(guān)鍵節(jié)點(diǎn) nodes，構(gòu)建虛樹
        slices.SortFunc(nodes, func(a, b int)int { return dfn[a] - dfn[b] })
        vt[root] = vt[root][:0] // 重置虛樹
        st = st[:1]
        for _, v := range nodes {
            isNode[v] = val
            if v == root {
                continue
            }
            vt[v] = vt[v][:0]
            lca := getLCA(st[len(st)-1], v) // 路徑的拐點(diǎn)（LCA）也加到虛樹中
            // 回溯，加邊
            forlen(st) > 1 && dfn[lca] <= dfn[st[len(st)-2]] {
                addVtEdge(st[len(st)-2], st[len(st)-1])
                st = st[:len(st)-1]
            }
            if lca != st[len(st)-1] { // lca 不在棧中（首次遇到）
                vt[lca] = vt[lca][:0]
                addVtEdge(lca, st[len(st)-1])
                st[len(st)-1] = lca // 加到棧中
            }
            st = append(st, v)
        }
        // 最后的回溯，加邊
        for i := 1; i < len(st); i++ {
            addVtEdge(st[i-1], st[i])
        }

         var dfs func(int)int
        dfs = func(v int) (size int) {
            // 如果 isNode[v] != t，那么 v 只是關(guān)鍵節(jié)點(diǎn)之間路徑上的「拐點(diǎn)」
            if isNode[v] == val {
                size = 1
            }
            for _, w := range vt[v] {
                sz := dfs(w)
                wt := dep[w] - dep[v] // 虛樹邊權(quán)
                // 貢獻(xiàn)法
                ans += int64(wt) * int64(sz) * int64(len(nodes)-sz)
                size += sz
            }
            return
        }

         rt := root
        if isNode[rt] != val && len(vt[rt]) == 1 {
            // 注意 root 只是一個哨兵，不一定在虛樹上，得從真正的根節(jié)點(diǎn)開始
            rt = vt[rt][0]
        }
        dfs(rt)
    }

     return
}

 func main() {
    n := 3
    edges := [][]int{{0, 1}, {1, 2}}
    group := []int{3, 2, 3}
    result := interactionCosts(n, edges, group)
    fmt.Println(result)
}

Python完整代碼如下：

# -*-coding:utf-8-*-

 import sys
sys.setrecursionlimit(10**6)

 def interactionCosts(n, edges, group):
    ans = 0

     g = [[] for _ in range(n)]
    for v, w in edges:
        g[v].append(w)
        g[w].append(v)

     dfn = [0] * n
    ts = 0
    pa = [[-1] * 17for _ in range(n)]
    dep = [0] * n

     def build(v, p):
        nonlocal ts
        dfn[v] = ts
        ts += 1
        pa[v][0] = p
        for w in g[v]:
            if w != p:
                dep[w] = dep[v] + 1
                build(w, v)

     build(0, -1)

     mx = n.bit_length()
    for i in range(mx - 1):
        for v in range(n):
            p = pa[v][i]
            if p != -1:
                pa[v][i+1] = pa[p][i]
            else:
                pa[v][i+1] = -1

     def uptoDep(v, d):
        k = dep[v] - d
        while k:
            step = (k & -k).bit_length() - 1
            v = pa[v][step]
            k -= (1 << step)
        return v

     def getLCA(v, w):
        if dep[v] > dep[w]:
            v, w = w, v
        w = uptoDep(w, dep[v])
        if w == v:
            return v
        for i in range(mx-1, -1, -1):
            pv, pw = pa[v][i], pa[w][i]
            if pv != pw:
                v, w = pv, pw
        return pa[v][0]

     nodesMap = {}
    for i, x in enumerate(group):
        nodesMap.setdefault(x, []).append(i)

     vt = [[] for _ in range(n)]
    isNode = [-1] * n

     def addVtEdge(v, w):
        vt[v].append(w)

     root = 0
    st = [root]

     for val, nodes in nodesMap.items():
        nodes.sort(key=lambda x: dfn[x])
        vt[root] = []
        st = [root]
        for v in nodes:
            isNode[v] = val
            if v == root:
                continue
            vt[v] = []
            lca = getLCA(st[-1], v)
            while len(st) > 1 and dfn[lca] <= dfn[st[-2]]:
                addVtEdge(st[-2], st[-1])
                st.pop()
            if lca != st[-1]:
                vt[lca] = []
                addVtEdge(lca, st[-1])
                st[-1] = lca
            st.append(v)
        for i in range(1, len(st)):
            addVtEdge(st[i-1], st[i])

         sys.setrecursionlimit(10**6)
        def dfs(v):
            nonlocal ans
            size = 1if isNode[v] == val else0
            for w in vt[v]:
                sz = dfs(w)
                wt = dep[w] - dep[v]
                ans += wt * sz * (len(nodes) - sz)
                size += sz
            return size

         rt = root
        if isNode[rt] != val and len(vt[rt]) == 1:
            rt = vt[rt][0]
        dfs(rt)

     return ans

 if __name__ == "__main__":
    n = 3
    edges = [[0, 1], [1, 2]]
    group = [3, 2, 3]
    result = interactionCosts(n, edges, group)
    print(result)

C++完整代碼如下：

  

  

   

  

  


 using namespace std;

 class Solution {
public:
    long long interactionCosts(int n, vector 
 
 int 
 >>& edges, vector< 
 int 
 >& group) { 
 
 
         long long ans =  
 0 
 ; 
 
 
 
 
          
 // 構(gòu)建鄰接表 
 
 
         vector 
 
 int 
 >> g(n); 
 
 
          
 for 
  (auto& e : edges) { 
 
 
              
 int 
  v = e[ 
 0 
 ], w = e[ 
 1 
 ]; 
 
 
             g[v].push_back(w); 
 
 
             g[w].push_back(v); 
 
 
         } 
 
 
 
 
          
 // 預(yù)處理 DFS 序、深度和倍增祖先 
 
 
         vector< 
 int 
 > dfn(n,  
 0 
 ); 
 
 
          
 int 
  ts =  
 0 
 ; 
 
 
         vector 
 
 int 
 ,  
 17 
 >> pa(n); 
 
 
         vector< 
 int 
 > dep(n,  
 0 
 ); 
 
 
 
 
         function 
 
 int 
 ,  
 int 
 )> build = [&]( 
 int 
  v,  
 int 
  p) { 
 
 
             dfn[v] = ts++; 
 
 
             pa[v][ 
 0 
 ] = p; 
 
 
              
 for 
  ( 
 int 
  w : g[v]) { 
 
 
                  
 if 
  (w != p) { 
 
 
                     dep[w] = dep[v] +  
 1 
 ; 
 
 
                     build(w, v); 
 
 
                 } 
 
 
             } 
 
 
         }; 
 
 
         build( 
 0 
 ,  
 -1 
 ); 
 
 
 
 
          
 int 
  mx =  
 32 
  - __builtin_clz(n);  
 // bits.Len(uint(n)) 
 
 
          
 for 
  ( 
 int 
  i =  
 0 
 ; i < mx -  
 1 
 ; i++) { 
 
 
              
 for 
  ( 
 int 
  v =  
 0 
 ; v < n; v++) { 
 
 
                  
 int 
  p = pa[v][i]; 
 
 
                  
 if 
  (p !=  
 -1 
 ) { 
 
 
                     pa[v][i +  
 1 
 ] = pa[p][i]; 
 
 
                 }  
 else 
  { 
 
 
                     pa[v][i +  
 1 
 ] =  
 -1 
 ; 
 
 
                 } 
 
 
             } 
 
 
         } 
 
 
 
 
          
 // 跳到指定深度 
 
 
         auto uptoDep = [&]( 
 int 
  v,  
 int 
  d) ->  
 int 
  { 
 
 
              
 int 
  k = dep[v] - d; 
 
 
             while (k >  
 0 
 ) { 
 
 
                  
 int 
  step = __builtin_ctz(k); 
 
 
                 v = pa[v][step]; 
 
 
                 k &= k -  
 1 
 ; 
 
 
             } 
 
 
              
 return 
  v; 
 
 
         }; 
 
 
 
 
          
 // 獲取 LCA 
 
 
         auto getLCA = [&]( 
 int 
  v,  
 int 
  w) ->  
 int 
  { 
 
 
              
 if 
  (dep[v] > dep[w]) { 
 
 
                 swap(v, w); 
 
 
             } 
 
 
             w = uptoDep(w, dep[v]); 
 
 
              
 if 
  (w == v)  
 return 
  v; 
 
 
              
 for 
  ( 
 int 
  i = mx -  
 1 
 ; i >=  
 0 
 ; i--) { 
 
 
                  
 int 
  pv = pa[v][i], pw = pa[w][i]; 
 
 
                  
 if 
  (pv != pw) { 
 
 
                     v = pv; 
 
 
                     w = pw; 
 
 
                 } 
 
 
             } 
 
 
              
 return 
  pa[v][ 
 0 
 ]; 
 
 
         }; 
 
 
 
 
          
 // 按點(diǎn)權(quán)分組節(jié)點(diǎn) 
 
 
          
 map 
 < 
 int 
 , vector< 
 int 
 >> nodesMap; 
 
 
          
 for 
  ( 
 int 
  i =  
 0 
 ; i < n; i++) { 
 
 
             nodesMap[group[i]].push_back(i); 
 
 
         } 
 
 
 
 
          
 // 虛樹 
 
 
         vector 
 
 int 
 >> vt(n); 
 
 
         vector< 
 int 
 > isNode(n,  
 -1 
 ); 
 
 
 
 
         auto addVtEdge = [&]( 
 int 
  v,  
 int 
  w) { 
 
 
             vt[v].push_back(w); 
 
 
         }; 
 
 
 
 
          
 const 
 int 
  root =  
 0 
 ; 
 
 
         vector< 
 int 
 > st; 
 
 
 
 
          
 // 處理每個點(diǎn)權(quán)組 
 
 
          
 for 
  (auto& [val, nodes] : nodesMap) { 
 
 
              
 // 按 DFS 序排序 
 
 
             sort(nodes.begin(), nodes.end(), [&]( 
 int 
  a,  
 int 
  b) { 
 
 
                  
 return 
  dfn[a] < dfn[b]; 
 
 
             }); 
 
 
 
 
              
 // 清空虛樹 
 
 
              
 for 
  ( 
 int 
  v : nodes) { 
 
 
                 vt[v].clear(); 
 
 
             } 
 
 
             vt[root].clear(); 
 
 
 
 
             st.clear(); 
 
 
             st.push_back(root); 
 
 
 
 
              
 // 構(gòu)建虛樹 
 
 
              
 for 
  ( 
 int 
  v : nodes) { 
 
 
                 isNode[v] = val; 
 
 
                  
 if 
  (v == root)  
 continue 
 ; 
 
 
 
 
                 vt[v].clear(); 
 
 
                  
 int 
  lca = getLCA(st.back(), v); 
 
 
 
 
                  
 // 回溯并加邊 
 
 
                 while (st.size() >  
 1 
  && dfn[lca] <= dfn[st[st.size() -  
 2 
 ]]) { 
 
 
                     addVtEdge(st[st.size() -  
 2 
 ], st.back()); 
 
 
                     st.pop_back(); 
 
 
                 } 
 
 
 
 
                  
 if 
  (lca != st.back()) { 
 
 
                     vt[lca].clear(); 
 
 
                     addVtEdge(lca, st.back()); 
 
 
                     st.back() = lca; 
 
 
                 } 
 
 
 
 
                 st.push_back(v); 
 
 
             } 
 
 
 
 
              
 // 添加剩余邊 
 
 
              
 for 
  ( 
 int 
  i =  
 1 
 ; i < st.size(); i++) { 
 
 
                 addVtEdge(st[i -  
 1 
 ], st[i]); 
 
 
             } 
 
 
 
 
              
 // DFS 遍歷虛樹計(jì)算貢獻(xiàn) 
 
 
             function< 
 int 
 ( 
 int 
 )> dfs = [&]( 
 int 
  v) ->  
 int 
  { 
 
 
                  
 int 
  size = (isNode[v] == val) ?  
 1 
  :  
 0 
 ; 
 
 
                  
 for 
  ( 
 int 
  w : vt[v]) { 
 
 
                      
 int 
  sz = dfs(w); 
 
 
                      
 int 
  wt = dep[w] - dep[v]; 
 
 
                     ans +=  
 1 
 LL * wt * sz * (nodes.size() - sz); 
 
 
                     size += sz; 
 
 
                 } 
 
 
                  
 return 
  size; 
 
 
             }; 
 
 
 
 
              
 // 找到真正的根節(jié)點(diǎn) 
 
 
              
 int 
  rt = root; 
 
 
              
 if 
  (isNode[rt] != val && vt[rt].size() ==  
 1 
 ) { 
 
 
                 rt = vt[rt][ 
 0 
 ]; 
 
 
             } 
 
 
             dfs(rt); 
 
 
         } 
 
 
 
 
          
 return 
  ans; 
 
 
     } 
 
 
 }; 
 
 
 
 
 int 
  main() { 
 
 
      
 int 
  n =  
 3 
 ; 
 
 
     vector 
 
 int 
 >> edges = {{ 
 0 
 ,  
 1 
 }, { 
 1 
 ,  
 2 
 }}; 
 
 
     vector< 
 int 
 > group = { 
 3 
 ,  
 2 
 ,  
 3 
 }; 
 
 
 
 
     Solution solution; 
 
 
     long long result = solution.interactionCosts(n, edges, group); 
 
 
     cout << result << endl; 
 
 
 
 
      
 return 
 0 
 ; 
 
 
 }

我們相信人工智能為普通人提供了一種“增強(qiáng)工具”，并致力于分享全方位的AI知識。在這里，您可以找到最新的AI科普文章、工具評測、提升效率的秘籍以及行業(yè)洞察。歡迎關(guān)注“福大大架構(gòu)師每日一題”，發(fā)消息可獲得面試資料，讓AI助力您的未來發(fā)展。

特別聲明：以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺“網(wǎng)易號”用戶上傳并發(fā)布，本平臺僅提供信息存儲服務(wù)。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.