2157. Сумма

 

Родители подарили Роману неориентированный связный взвешенный граф с n вершинами и n – 1 ребрами. Роман хочет найти суммарную длину всех путей в графе. Длина пути равна сумме длин ребер в нем. Роман считает, что путь из u в v такой же как и из v в u, поэтому он не различает их.

 

Вход. Первая строка содержит количество вершин в графе n (2 ≤ n ≤ 105). Следующие n – 1 строк описывают ребра. Каждая строка содержит три целых числа: номера вершин, соединенных ребром (вершины пронумерованы числами от 1 до n), и вес ребра.

 

Выход. Вывести сумму длин всех путей, вычисленную по модулю 109.

 

Пример входа 1

Пример выхода 1

3

1 2 1

1 3 3

8

 

 

Пример входа 2

Пример выхода 2

6

1 2 5

1 3 1

2 4 2

2 5 4

2 6 3

90

 

В первом примере все пути на дереве: 1 – 2, 1 – 3, 2 – 1 – 3, сумма их длин равна 1 + 3 + 4 = 8.

 

РЕШЕНИЕ

графы – поиск в глубину - дерево

 

Анализ алгоритма

Запустим поиск в глубину из некоторой вершины дерева. Рассмотрим ребро (u, v) дерева с весом w. Пусть количество вершин в поддереве с корнем v равно с. Тогда в дереве с одной стороны ребра находится c вершин, а с другой n – c вершин. Ребро (u, v) входит в c * (n – c) различных путей. Поэтому вклад этого ребра в сумму длин всех путей составляет c * (n – c) * w. Остается перебрать поиском в глубину все ребра и просуммировать их вклад в общую сумму длин.

 

Пример

Графы, приведенные в примерах, имеют вид:

 

Рассмотрим вклады ребер в общую сумму длин всех путей в первом примере.

Ребро (1, 2) весом 1 принадлежит двум путям:

·        1 – 2;

·        2 – 1 – 3;

Его вклад в общую сумму составляет 1 * 2 * 1 = 2.

Ребро (1, 3) весом 3 принадлежит двум путям:

·        1 – 3;

·        2 – 1 – 3;

Его вклад в общую сумму составляет 2 * 1 * 3 = 6.

Сумма длин всех путей равна 2 + 6 = 8.

 

Во втором примере рассмотрим вклад ребра (1, 2) весом 5 в общую сумму длин всех путей.

Количество вершин в поддереве с корнем 2 равно с = 4 (включая саму вершину 2). Тогда с другой стороны ребра (1, 2) находится n – c = 6 – 4 = 2 вершины. Следовательно количество разных путей, содержащих ребро (1, 2), равно c * (n – c) = 4 * 2 = 8. Действительно, такими путями будут

1 – 2, 1 – 2 – 4, 1 – 2 – 5, 1 – 2 – 6,

3 – 1 – 2, 3 – 1 – 2 – 4, 3 – 1 – 2 – 5, 3 – 1 – 2 – 6

Вклад ребра (1, 2) весом 5 в сумму длин всех путей составляет c * (n – c) * w = 4 * 2 * 5 = 40.

 

Реализация алгоритма

Входной взвешенный граф храним в списке смежности g.

 

#define MOD 1000000000;

vector<vector<pair<int,int> > > g;

 

Функция dfs реализует поиск в глубину из вершины v возвращает количество вершин в поддереве с корнем v (включая саму вершину v). Подсчет этих вершин происходит в переменной cnt. Изначально положим cnt = 1, считая что в поддерево включена сама вершина v.

 

int dfs(int v, int p = -1)

{

  int cnt = 1;

  for (auto edge : g[v])

  {

    int to = edge.first;

    int w = edge.second;

 

Рассмотрим ребро (v, to) с весом w. Вычисляем количество вершин c в поддереве с корнем to. Таким образом в дереве с одной стороны ребра находится c вершин, а с другой n – c вершин. Ребро (v, to) входит в c * (n – c) различных путей. Поэтому вклад этого ребра в сумму длин всех путей составляет c * (n – c) * w.

 

    if (to != p)

    {

      int c = dfs(to, v);

      res = (res + 1LL * c * (n - c) * w) % MOD;

      cnt += c;

    }

  }

  return cnt;

}

 

Основная часть программы. Читаем взвешенный граф в список смежности g.

 

scanf("%d", &n);

g.resize(n + 1);

for (i = 1; i < n; i++)

{

  scanf("%d %d %d", &u, &v, &d);

  g[u].push_back({v, d});

  g[v].push_back({u, d});

}

 

Запускаем поиск в глубину из вершины 1. Вершины графа нумеруются с 1 до n.

 

dfs(1);

 

Выводим ответ.

 

printf("%lld\n",res);

 

Java реализация

 

import java.util.*;

import java.io.*;

 

class Edge

{

  int to;

  int weight;

  public Edge(int to, int weight)

  {

    this.to = to;

    this.weight = weight;

  }

}

 

public class Main

{

  static int MOD = 1000000000;

  static ArrayList<Edge>[] g;    

  static int n, m;

  static long res;

 

  static int dfs(int v, int p)

  {

    int cnt = 1;

    for(Edge edge : g[v])

    {

      int to = edge.to;

      int w = edge.weight;

      if (to != p)

      {

        int c = dfs(to, v);

        res = (res + 1L * c * (n - c) * w) % MOD;

        cnt += c;

      }

    }

    return cnt;

  }

 

  public static void main(String[] args)

  {

    FastScanner con = new FastScanner(System.in);

    n = con.nextInt();

    g = new ArrayList[n+1]; // unchecked

 

    for (int i = 0; i <= n; i++)

      g[i] = new ArrayList<Edge>();

 

    for (int i = 1; i < n; i++)

    {

      int u = con.nextInt();

      int v = con.nextInt();

      int d = con.nextInt();

      g[u].add(new Edge(v,d));

      g[v].add(new Edge(u,d));

    }

   

    dfs(1,-1);

    System.out.println(res);   

  }

}  

 

class FastScanner

{

  BufferedReader br;

  StringTokenizer st;

 

  public FastScanner(InputStream inputStream)

  {

    br = new BufferedReader(new InputStreamReader(inputStream));

    st = new StringTokenizer("");

  }

 

  public String next()

  {

    while (!st.hasMoreTokens())

    {

      try

      {

        st = new StringTokenizer(br.readLine());

      } catch (Exception e)

      {

        return null;

      }

    }

    return st.nextToken();

  }

 

  public int nextInt()

  {

    return Integer.parseInt(next());

  }

}

 

Python реализация

 

MOD = 1000000000

 

def dfs(v, p = -1):

  global res

  cnt = 1

  for to, w in g[v]:

    if to != p:

      c = dfs(to, v)

      res = (res + c * (n - c) * w) % MOD

      cnt += c

  return cnt

 

n = int(input())

g = [[] for _ in range(n + 1)]

res = 0

 

for _ in range(n - 1):

  u, v, d = map(int, input().split())

  g[u].append((v, d))

  g[v].append((u, d))

 

dfs(1)

 

print(res)