Cəm#2157

Cəm (Həll təhlili)

İstənilən ağacın zirvəsindən dərinlik üzrə axtarış başladaq. $(u, v)$ çəkili üzünü nəzərdən keçirdək. Deyək ki, $v$ kök olan alt ağacda olan zirvələrin sayı $c$ -dir. Onda bir tərəfdəki ucluqda $c$ zirvə, digər tərəfdə isə $n - c$ n - c zirvə olur. $(u, v)$ üzü $c \cdot (n - c)$ c \cdot (n - c) müxtəlif zirvə cütləri arasında olan yollara düşür. Beləliklə, $(u, v)$ üzünün bütün yolların cəmi uzunluğuna olan təsiri $c \cdot (n - c) \cdot w$ c \cdot (n - c) \cdot w-ya bərabərdir. Dərinlik üzrə axtarış vasitəsilə bütün üzülləri yoxlamaq və onların cəmi uzunluqlara olan təsirini toplamaq qalır.

Nümunə

Nümunələrdə verilmiş qraflar belə görünür:

Birinci nümunədə üzüllərin bütün yolların cəmi uzunluğuna olan təsirini nəzərdən keçirək.

Çəkisi $1$ olan $(1, 2)$ üzü iki yola daxildir:

$1 - 2$ 1 - 2;
$2 - 1 - 3$ 2 - 1 - 3;

Onun cəmi uzunluğa olan təsiri $1 \cdot 2 \cdot 1 = 2$ 1 \cdot 2 \cdot 1 = 2-yə bərabərdir.

Çəkisi $3$ olan $(1, 3)$ üzü iki yola daxildir:

$1 - 3$ 1 - 3;
$2 - 1 - 3$ 2 - 1 - 3;

Onun cəmi uzunluğa olan təsiri $2 \cdot 1 \cdot 3 = 6$ 2 \cdot 1 \cdot 3 = 6-yə bərabərdir.

Bütün yolların cəmi uzunluğu $2 + 6 = 8$ 2 + 6 = 8-ə bərabərdir.

İkinci nümunədə $(1, 2)$ üzü çəkisi $5$ olanın bütün yolların cəmi uzunluğuna təsirini nəzərdən keçirək.

$v = 2$ v = 2 kök olan alt ağacda zirvələrin sayı $с = 4$ с = 4-dir (öz zirvəsi $2$ -i də daxil olmaqla). Onda $(1, 2)$ üzünün digər tərəfində $n - c = 6 - 4 = 2$ n - c = 6 - 4 = 2 zirvə var. Beləliklə, $c * (n - c) = 4 * 2 = 8$ c * (n - c) = 4 * 2 = 8 müxtəlif yol var ki, onlar $(1, 2)$ üzündən keçir. Doğrudan da, bu yolların hamısı $1$ zirvəsinin alt ağacında olmayan zirvələrdən ibarət olanlərdir. Beləliklə:

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, 1 - 2 - 4, 1 - 2 - 5, 1 - 2 - 6, \\ 3 - 1 - 2, 3 - 1 - 2 - 4, 3 - 1 - 2 - 5, 3 - 1 - 2 - 6

Çəkisi $5$ olan $(1, 2)$ üzünün bütün yolların cəmi uzunluğuna təsiri belədir:

c \cdot (n - c) \cdot w = 4 \cdot 2 \cdot 5 = 40

c \cdot (n - c) \cdot w = 4 \cdot 2 \cdot 5 = 40

Alqoritmin həyata keçirilməsi

MOD dəyərini müəyyən edək.

#define MOD 1000000000

Giriş çəkili qrafını qonşuluq siyahısına $g$ saxlayaq.

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

Funksiya dfs $v$ -dən başlanan dərinlik üzrə axtarışı həyata keçirir və kökü $v$ olan alt ağacda zirvələrin sayını qaytarır (öz zirvəsi $v$ daxil olmaqla). Bu zirvələrin sayı $c n t$ dəyişənində saxlanılır. Əvvəlcə $c n t = 1$ cnt = 1 olur, çünki alt ağac artıq özündə $v$ zirvəsini ehtiva edir.

int dfs(int v, int p = -1)
{
  int cnt = 1;
  for (auto edge : g[v])
  {
    int to = edge.first;
    int w = edge.second;

C++

Çəkisi $w$ olan $(v, t o)$ (v, to) üzünü nəzərə alaq. $t o$ zirvəsinin kökü olduğu alt ağacda zirvələrin sayını $c$ hesablayırıq. Onda bir tərəfdə üzü $c$ zirvəsi var, digərində isə $n - c$ n - c zirvələri var. $(v, t o)$ (v, to) üzü $c \cdot (n - c)$ c \cdot (n - c) müxtəlif zirvə cütləri arasında olan yollara daxildir.

Beləliklə, $(v, t o)$ (v, to) üzünün bütün yolların cəmi uzunluğuna olan təsiri belədir:

c \cdot (n - c) \cdot w

c \cdot (n - c) \cdot w

    if (to != p)
    {
      int c = dfs(to, v);
      res = (res + 1LL * c * (n - c) * w) % MOD;
      cnt += c;
    }
  }
  return cnt;
}

C++

Proqramın əsas hissəsi. Giriş çəkili qrafını qonşuluq siyahısına $g$ oxuyuruq.

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});
}

C++

Dərinlik üzrə axtarışı $1$ zirvəsindən başlatmaq. Qraf zirvələri $1$ -dən $n$ -ə qədər nömrələnir.

dfs(1);

Cavabı göstərmək.

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

Java reallaşdırılması

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());
  }
}

Java

Python reallaşdırılması

MOD dəyərini müəyyən edək.

MOD = 1000000000

def dfs(v, p = -1):
  global res
  cnt = 1
  for to, w in g[v]:

Beləliklə, $(v, t o)$ (v, to) üzünün bütün yolların cəmi uzunluğuna olan təsiri belədir:

c \cdot (n - c) \cdot w

c \cdot (n - c) \cdot w

    if to != p:
      c = dfs(to, v)
      res = (res + c * (n - c) * w) % MOD
      cnt += c
  return cnt

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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))

Python

Dərinlik üzrə axtarışı $1$ zirvəsindən başlatmaq. Qraf zirvələri $1$ -dən $n$ -ə qədər nömrələnir.

dfs(1)

Cavabı göstərmək.

print(res)