•Article•4 ay öncə

Ağaclar

Ağaclar alqoritmlərdə əsas verilən strukturlarından biridir və müxtəlif məsələlərdə tez-tez rast gəlinir.

Ağac — əlaqəli, dövrəsiz, istiqamətsiz qrafdır.

Bir $G = (V, E)$ qrafı aşağıdakı xüsusiyyətləri ödəyirsə, ona ağac deyilir:

Əlaqəli — qrafdakı istənilən iki zirvə arasında yol mövcuddur.
Dövrəsiz — qraf heç bir dövr (cycle) ehtiva etmir.

$n$ zirvəli ağacda həmişə dəqiq olaraq $n - 1$ kənar (edge) olur.

Ağacın Əsas Xüsusiyyətləri

1. Əlaqəlilik və Yolların Təkliyi

Ağacda istənilən iki zirvə arasında unikal (tək) yol mövcuddur.

2. Kənarların Sayı

Hər hansı ağac üçün:

∣ E ∣ = ∣ V ∣ - 1

3. Dövr yoxdur

Ağaca əlavə edilən istənilən kənar mütləq dövr yaradır.

4. Kök (kök verilmiş ağac üçün)

Əgər bir zirvə kök kimi seçilərsə, ağac kökdən övladlara doğru istiqamətlənmiş olur. Bu, rekursiv keçidlərdə və alqoritmlərdə ( $D FS$ , $L C A$ və s.) istifadə olunur.

5. Alt ağaclar

Hər hansı zirvə və onun nəslindən olan bütün zirvələr alt ağac yaradır. Alt ağac özü də ağacdır.

6. Yarpaqlar

Heç bir övladı olmayan (kök verilmiş ağacda) zirvələrə yarpaq deyilir.

7. Dərinlik və Hündürlük

Dərinlik — kökdən həmin zirvəyə olan məsafə.
Hündürlük — ağacdakı maksimum dərinlik.

8. Ağacın Mərkəzi

Mərkəz — bütün digər zirvələrə qədər olan maksimal məsafəni minimallaşdıran zirvə (və ya bitişik zirvələr cütü)dir.

Ağacın Alternativ Tərifləri

Ağac üçün aşağıdakı təriflər bir-birinə ekvivalentdir və müxtəlif kontekstlərdə istifadə oluna bilər:

Hər hansı bir kənarın silinməsi ilə qraf əlaqəsini itirən dövrəsiz qraf.
$n$ zirvəsi və $n - 1$ kənarı olan əlaqəli qraf.
$n - 1$ kənarı olan və dəqiq bir komponentdən ibarət dövrəsiz qraf.

Ağacların Koddakı Təsviri

Məsələnin növündən və ağacın tipindən (ümumi, binar, kök verilmiş və s.) asılı olaraq müxtəlif verilən strukturlarından istifadə olunur:

1. Qonşuluq siyahısı (Adjacency Lists)

Bu yanaşma yarışma tipli məsələlərdə və istiqamətli/istiqamətsiz ağaclarla işləyərkən çox istifadə olunur.

int n;
vector<vector<int>> tree(n); // n zirvəli ağac

// u və v zirvələri arasında kənar əlavə etmək
tree[u].push_back(v);
tree[v].push_back(u); // istiqamətsiz ağac üçün

2. Valideyn massivi (Parent Array)

Çox yığcam təmsil formasıdır, xüsusilə ağac artıq qurulmuşdursa istifadə olunur.

vector<int> parent(n); // parent[i] --- i zirvəsinin valideyni
// əgər i kökdürsə, adətən parent[i] = -1 və ya 0 seçilir

3. Göstəricilər / Strukturlar (OOP üslubu)

Xüsusilə binar ağaclar, trie-lər, dekoratorlar qurarkən Python/Java/C++ dillərində obyekt-yönlü proqramlaşdırma ilə istifadə olunur.

Binar ağac:

struct Node 
{
  int val;
  Node* left;
  Node* right;
  Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

Ümumi ağac:

struct Node 
{
  int val;
  vector<Node*> children;
  Node(int v) : val(v) {}
};

Qrafın qonşuluq matrisası $g$ və ziyarət statusunu saxlayan $u se d$ massivini elan edək.

#define MAX 110
int g[MAX][MAX], used[MAX];

dfs funksiyası zirvə $v$ -dən başlayaraq dərinlikə görə axtarış aparır. $v$ zirvəsinin valideyni $p$ -dir. Əgər sikl aşkar edilərsə, $f l a g$ dəyişəni $1$ edilir.

void dfs(int v, int p)
{

Əgər qraf artıq ağac deyilsə $(f l a g = 1)$ , axtarışı davam etdirməyə ehtiyac yoxdur.

  if (flag) return;

Zirvə $v$ ziyarət olunmuş kimi işarələnir.

  used[v] = 1;

Zirvə $v$ ziyarət olunubsa, $c$ dəyişəni $1$ vahid artırılır.

  c++;

Kənar $(v, i)$ geri kənar (back edge) olacaq və sikl yaradacaq, əgər $i \neq = p$ və $i$ zirvəsi artıq ziyarət olunubsa $(u se d [i] = 1)$ . Əgər sikl aşkar edilərsə, $f l a g = 1$ təyin olunur. Əgər sikl yoxdursa, axtarış $i$ zirvəsindən davam etdirilir.

  for(int i = 0; i < n; i++)
    if ((i != p) && g[v][i])
      if(used[i]) flag = 1; else dfs(i,v);
}

Proqramın əsas hissəsi. Giriş verilənlərini oxu.

scanf("%d",&n); 
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
  scanf("%d",&g[i][j]);

Dərinlikə görə axtarış zamanı ziyarət edilmiş zirvələrin sayı $c$ dəyişənində saxlanılır. Əgər qrafda sikl yoxdursa, $f l a g = 0$ olur. Əgər sikl aşkar edilərsə, $f l a g = 1$ təyin olunur.

c = 0;
flag = 0;

Bütün zirvələr başlanğıcda ziyarət olunmamış kimi işarələnir ( $u se d$ massivini sıfırla).

memset(used,0,sizeof(used));

Dərinlikə görə axtarışı $0$ -cı zirvədən başlat. Bu zirvə ağacın köküdür və valideyni yoxdur. Ona görə də dfs funksiyasına ikinci arqument kimi $- 1$ verilir.

dfs(0,-1);

Əgər $f l a g = 1$ (sikl var) və ya $c \neq = n$ (qraf bağlı deyil) olarsa, bu, qrafın ağac olmadığını göstərir.

if (flag || (c != n)) printf("NO\n"); else printf("YES\n");

Python implementasiyası — 1) və 3) şərtlərin yoxlanılması

dfs funksiyası zirvə $v$ -dən başlayaraq dərinlikə görə axtarış aparır. $v$ zirvəsinin valideyni $p$ -dir. Əgər sikl aşkar edilərsə, $f l a g$ dəyişəni $1$ edilir.

def dfs(v, p):

Funksiyada istifadə olunan qlobal dəyişənləri elan et.

  global flag, c

Əgər qraf artıq ağac deyilsə $(f l a g = 1)$ , axtarışı davam etdirməyə ehtiyac yoxdur.

  if flag: return

Zirvə $v$ ziyarət olunmuş kimi işarələnir.

  used[v] = 1

Zirvə $v$ ziyarət olunub, $c$ dəyişəni $1$ artırılır.

  c += 1

Əgər $i \neq = p$ və $i$ zirvəsi artıq ziyarət olunubsa $(u se d [i] = 1)$ , onda $(v, i)$ kənarı geri kənardır və sikl yaradır. Əgər sikl aşkar edilərsə, $f l a g = 1$ qoyulur. Əks halda, axtarış $i$ zirvəsindən davam etdirilir.

  for i in range(n):
    if i != p and g[v][i]:
      if used[i]: flag = 1
      else: dfs(i, v)

Proqramın əsas hissəsi. $n$ dəyərini oxu.

n = int(input())

Dərinlikə görə axtarış zamanı ziyarət olunan zirvələrin sayı $c$ dəyişənində saxlanılır. Əgər qrafda sikl yoxdursa, $f l a g = 0$ . Sikl aşkar edilərsə, $f l a g = 1$ olur.

c = 0
flag = 0

Bütün zirvələr başlanğıcda ziyarət olunmamışdır (sıfırla başlanır).

used = [0] * n

Sıfırlarla dolu qonşuluq matrisi $g$ yarat.

g = [[0] * n for _ in range(n)]

Qonşuluq matrisini oxu.

for i in range(n):
  g[i] = list(map(int, input().split()))

Dərinlikə görə axtarışı $0$ zirvəsindən başlat. Bu zirvə ağacın kökü olduğuna görə onun valideyni yoxdur. dfs funksiyasına ikinci arqument olaraq $- 1$ ötürülür.

dfs(0, -1)

Əgər geri kənar varsa $(f l a g = 1)$ və ya qraf əlaqəli deyilsə $(c \neq = n)$ , o zaman qraf ağac deyil.

if flag or c != n:
  print("NO")
else:
  print("YES")

Qrafın qonşuluq matrisini $g$ və istifadə olunmuş zirvələri saxlayan $u se d$ massivini elan et.

#define MAX 101
int g[MAX][MAX], used[MAX];

dfs funksiyası $v$ zirvəsindən dərinlikə görə axtarış həyata keçirir.

void dfs(int v)
{

Zirvəni ziyarət olunmuş kimi işarələ.

  used[v] = 1;

Zirvə $v$ ziyarət olundu, $c$ dəyişənini $1$ artır.

  c++;

$v$ zirvəsindən keçid mümkün olan bütün $i$ zirvələrini yoxla. $v \to i$ keçidi mümkündür əgər:

$(v, i)$ kənarı mövcuddur, yəni $g [v] [i] = 1$ ;
$i$ zirvəsi hələ ziyarət olunmayıb $(u se d [i] = 0)$

Əgər hər iki şərt ödənilirsə, dərinlikə görə axtarışı $i$ zirvəsindən davam etdir.

  for (int i = 1; i <= n; i++)
    if (g[v][i] && !used[i]) dfs(i);
}

Proqramın əsas hissəsi. $n$ dəyərini oxu.

scanf("%d", &n);

Qrafdakı kənarların sayını $E d g es$ dəyişənində saxla.

Edges = 0;

Bütün zirvələri başlanğıcda ziyarət olunmamış kimi işarələ (massivi sıfırla).

memset(used, 0, sizeof(used));

Qonşuluq matrisini $g$ oxu. Kənarların sayını hesabla.

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
  scanf("%d", &g[i][j]);
  Edges += g[i][j];
}

Qraf yönsüz olduğuna görə $(u, v)$ və $(v, u)$ kənarları eyni sayılır. Ona görə $E d g es$ dəyişənini $2$ -yə böl.

Edges /= 2;

Dərinlikə görə axtarış zamanı ziyarət olunan zirvələrin sayını $c$ dəyişənində saxla.

c = 0;

Dərinlikə görə axtarışı $1$ -ci zirvədən başlat.

dfs(1);

Qraf ağacdır, əgər kənarların sayı $n - 1$ -ə bərabərdirsə və o, bağlıdırsa $(c = n)$ .

if ((Edges == n - 1) && (c == n)) printf("YES\n");
else printf("NO\n");

Python implementasiyası — 1) və 2) şərtlərinin yoxlanması

dfs funksiyası $v$ zirvəsindən dərinliyə görə axtarışı həyata keçirir.

def dfs(v):
  global c

Zirvə $v$ ziyarət olunduğu kimi işarələnir.

  used[v] = 1

Zirvə $v$ ziyarət olunubsa, $c$ dəyişəni $1$ artırılır.

  c += 1

Zirvə $v$ -dən çıxan keçidlər üzrə $i$ zirvələrinə baxılır. $v \to i$ keçidi mümkündür, əgər:

$(v, i)$ kənarı mövcuddursa, yəni $g [v] [i] = 1$ ;
$i$ zirvəsi hələ ziyarət olunmayıbsa $(u se d [i] = 0)$ .

Əgər hər iki şərt ödənirsə, axtarış $i$ zirvəsindən davam etdirilir.

  for i in range(1, n + 1):
    if g[v][i] and not used[i]: dfs(i)

Proqramın əsas hissəsi. $n$ dəyərini oxu.

n = int(input())

Qrafdakı kənarların sayını $E d g es$ dəyişənində saxla.

Edges = 0

Bütün zirvələr ilkin olaraq ziyarət olunmamış sayılır (massiv $u se d$ sıfırlarla başlanır).

used = [0] * (n + 1)

Sıfırlarla doldurulmuş başlanğıc vəziyyətində qonşuluq matrisası $g$ yaradılır.

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

Qonşuluq matrisası $g$ oxunur. Qrafdakı kənarların sayı $E d g es$ dəyişənində toplanır.

for i in range(1, n + 1):
  g[i] = [0] + list(map(int, input().split()))
  Edges += sum(g[i])

Qraf istiqamətsiz olduğuna görə, $(u, v)$ və $(v, u)$ kənarları eyni sayılır. Bu səbəbdən $E d g es$ dəyişəninin dəyəri $2$ -yə bölünür.

Edges //= 2

Dərinlik üzrə axtarış zamanı ziyarət edilmiş zirvələrin sayı $c$ dəyişənində saxlanılır.

c = 0

Dərinlik üzrə axtarışı $1$ -ci zirvədən başlat.

dfs(1)

Əgər qrafda $n - 1$ kənar varsa və o əlaqəlidirsə $(c = n)$ , bu halda qraf ağacdır.

if Edges == n - 1 and c == n:
  print("YES")
else:
  print("NO")

Sizə tsiklsiz sadə qoşulmuş qraf – bir ağac verilir.

Tapşırıq ondan ibarətdir ki, maksimum neçə kənarı silmək olar ki, nəticədə alınan meşədə (forest) hər bir əlaqəli komponent cüt sayda zirvədən ibarət olsun.

Məsələn, aşağıda göstərilən $4$ zirvəli ağacdan maksimum $1$ kənar silmək olar ki, alınan meşədə bütün komponentlər cüt ölçülü olsun.

Giriş. Birinci sətrdə iki tam ədəd $n (2 \leq n \leq 100, n$ cütdür $)$ və $m$ — ağacdakı zirvə və kənarların sayı verilir. Sonrakı $m$ sətrin hər birində iki tam ədəd — ağacdakı kənarları təşkil edən zirvələr verilir. Ağacın kökü $1$ -ci zirvədir.

Çıxış. Cüt komponentlərdən ibarət meşə almaq üçün silinə biləcək maksimum kənarların sayını çap edin.

Problemi aç

Nümunə

Nümunədə verilmiş ağacı nəzərdən keçirək. Hər bir zirvənin yanında, həmin zirvənin kök olduğu alt ağacın ölçüsü qeyd olunub. Zirvələr $1, 3$ və $6$ -nın alt ağacları cüt sayda zirvəyə malikdir. Zirvə $1$ kök olduğundan və onu valideynə birləşdirən kənar olmadığından, $(1, 3)$ və $(1, 6)$ kənarlarını silirik.

Ağac cüt sayda zirvəsi olan $3$ əlaqəli komponentə bölünüb.

Massivləri elan edirik.

#define MAX 101
int g[MAX][MAX], used[MAX];

dfs funksiyası $v$ zirvəsindən başlayaraq dərinlik üzrə axtarış aparır və $v$ kök olduqda onun alt ağacındakı zirvələrin sayını qaytarır.

int dfs(int v)
{
  used[v] = 1;

$s$ dəyişənində $v$ zirvəsinin alt ağacındakı zirvələrin sayını hesablayırıq.

  int s = 1;

$v$ zirvəsinin bütün qonşuları $i$ üzərində iterasiya aparırıq. Əgər $i$ zirvəsi istifadə olunmayıbsa, $df s (i)$ funksiyasını çağırıb nəticəni $s$ -ə əlavə edirik.

  for (int i = 1; i <= n; i++)
    if (g[v][i] && !used[i]) s += dfs(i);

Əgər alt ağacın ölçüsü $s$ cütdürsə, $v$ və onun valideyni arasındakı kənar silinir.

  if (s % 2 == 0) res++;

$v$ zirvəsinin kök olduğu alt ağacdakı zirvələrin sayını qaytar.

  return s;
}

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

scanf("%d %d", &n, &m);
for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a][b] = g[b][a] = 1;
}

Dərinlik üzrə axtarışı $1$ zirvəsindən başlayırıq. $res$ dəyişənində silinmiş kənarların sayını hesablayırıq.

res = 0;
dfs(1);

Çünki $1$ zirvəsinin valideynə birləşdirən kənar yoxdur, nəticə olaraq $res - 1$ çap olunur.

printf("%d\n", res - 1);

Python reallaşdırması

dfs funksiyası $v$ zirvəsindən başlayaraq dərinlik üzrə axtarış aparır və $v$ kök olduqda onun alt ağacındakı zirvələrin sayını qaytarır.

def dfs(v):
  used[v] = 1

$s$ dəyişənində $v$ zirvəsinin alt ağacındakı zirvələrin sayını hesablayırıq.

  s = 1

Uşaqlar $i$ üzrə dövr qururuq. $df s (i)$ funksiyasının qaytardığı dəyəri $s$ -ə əlavə edirik.

  for i in range(1, n + 1):
    if g[v][i] and not used[i]:
      s += dfs(i)

Əgər alt ağacın ölçüsü $s$ cütdürsə, $v$ ilə onun valideyni arasındakı kənarı silirik.

  if s % 2 == 0:
    global res
    res += 1

$v$ kök olduqda alt ağacındakı zirvələrin sayını qaytarırıq.

  return s

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

n, m = map(int, input().split())
g = [[0] * (n + 1) for _ in range(n + 1)]
used = [0] * (n + 1)

for _ in range(m):
  a, b = map(int, input().split())
  g[a][b] = g[b][a] = 1

$1$ zirvəsindən başlayaraq dərinlik üzrə axtarış aparırıq. $res$ dəyişənində silinmiş kənarların sayını hesablayırıq.

res = 0
dfs(1)

Çünki $1$ zirvəsinin valideynə birləşdirən kənarı yoxdur, nəticə olaraq $res - 1$ çap olunur.

print(res - 1)

Ağac qonşuluq siyahısı $g$ ilə təqdim olunur.

vector<vector<int> > g;

dfs funksiyası $v$ zirvəsindən dərinlik üzrə axtarış həyata keçirir və $v$ zirvəsindən başlayan alt-ağacda olan qovşaqların sayını qaytarır. $p$ — dərinlik üzrə axtarışda $v$ zirvəsinin valideynidir.

int dfs(int v, int p)
{

İlkin olaraq, $v$ zirvəsindən başlayan alt-ağac yalnız $v$ qovşağını ehtiva edir.

  sum[v] = 1;

$v \to t o$ qırağını nəzərdən keçirək. Əgər $t o \neq = p$ -dirsə, onda $s u m [v]$ dəyərinə $t o$ zirvəsindən başlayan alt-ağacdakı qovşaqların sayını əlavə edirik.

  for (int to : g[v])
    if (to != p) sum[v] += dfs(to, v);

$v$ zirvəsindən başlayan alt-ağacda olan qovşaqların sayını qaytar.

  return sum[v];
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxu və ağacı qur.

scanf("%d", &n);
g.resize(n + 1);

for (i = 2; i <= n; i++)
{
  scanf("%d", &x);

$i$ işçisinin birbaşa rəhbəri $x$ -dir.

  g[i].push_back(x);
  g[x].push_back(i);
}

Dərinlik üzrə axtarışı $1$ -ci zirvədən başlat.

sum.resize(n + 1);
dfs(1, -1);

Cavabı çap et. $i$ işçisinin tabeliyində olanların sayı $s u m [i] - 1$ -ə bərabərdir.

for (i = 1; i <= n; i++)
  printf("%d ", sum[i] - 1);
printf("\n");

Java dili ilə reallaşdırma


import java.util.*;

public class Main
{
  static ArrayList<Integer>[] g;	// ağacın siyahı ilə təsviri
  static int sum[];                 // hər bir işçi üçün alt-ağacdakı qovşaq sayı
  static int n;                     // işçilərin sayı
  
  static int dfs(int v, int p)
  {
    sum[v] = 1;
    for(int to : g[v])
      if (to != p) sum[v] += dfs(to, v);
    return sum[v];
  }
  
  @SuppressWarnings("unchecked")
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    g = new ArrayList[n + 1]; // işçi nömrələri 1-dən başlayır
    sum = new int[n + 1];

    for (int i = 0; i <= n; i++)
      g[i] = new ArrayList<Integer>();

    for (int i = 2; i <= n; i++)
    {
      int x = con.nextInt();
      g[i].add(x);   
      g[x].add(i);   
    }
    
    dfs(1, -1); 
    for (int i = 1; i <= n; i++)
      System.out.print(sum[i] - 1 + " "); 
    System.out.println();
    con.close();
  }
}

Python ilə reallaşdırma

Rekursiya üçün stekin ölçüsünü artırın.

import sys
sys.setrecursionlimit(1000000)

dfs funksiyası $v$ qovşağından başlayaraq dərinlik-öncə axtarış aparır və $v$ qovşağında kök salan alt-ağacdakı qovşaq sayını qaytarır. $p$ isə $v$ qovşağının valideynidir.

def dfs(v, p):

Əvvəlcə, $v$ qovşağında kök salan alt-ağac yalnız özünü ehtiva edir.

  sum[v] = 1

$v \to t o$ istiqamətli kənarını nəzərdən keçir. Əgər $t o \neq = p$ -dirsə, $t o$ qovşağında kök salan alt-ağacdakı qovşaq sayını $s u m [v]$ -ə əlavə et.

  for to in g[v]:
    if to != p: sum[v] += dfs(to, v)

$v$ qovşağında kök salan alt-ağacdakı qovşaq sayını qaytar.

  return sum[v]

Proqramın əsas hissəsi. İşçilərin sayını oxuyun.

n = int(input())

Qrafın qonşuluq siyahısını $g$ kimi başladın.

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

Giriş məlumatını oxuyun. Ağacı qurun.

lst = list(map(int, input().split()))
for i in range(2, n+1):
  a = lst[i-2]

$i$ -ci işçi üçün ( $i \geq 2$ ), onun birbaşa rəhbəri $a$ -dır.

  g[a].append(i)
  g[i].append(a)

$s u m$ siyahısını başladın.

sum = [0] * (n + 1)

Dərinlik-öncə axtarışı $1$ qovşağından başladın.

dfs(1, -1)

Cavabı çap edin. $i$ -ci işçinin tabeliyində olanların sayı $s u m [i] - 1$ -ə bərabərdir.

for i in range(1, n + 1):
  print(sum[i] - 1, end=" ")

Daxil edilən ağacı qonşuluq siyahısı ( $g$ ) kimi saxlayın. Mənbədən hər bir zirvəyə olan ən qısa məsafələri $d i s t$ massivində saxlayın.

vector<vector<int>> g;
vector<int> dist;

dfs funksiyası zirvə $v$ -dən dərinlik üzrə axtarış aparır. Mənbədən zirvə $v$ -yə olan ən qısa məsafə $d$ -dir. Zirvə $v$ -nin dərinlik üzrə axtarışdakı valideyni $p$ -dir.

void dfs(int v, int d, int p = -1)
{

Mənbədən zirvə $v$ -yə olan ən qısa məsafəni $d i s t [v]$ -də saxlayın.

  dist[v] = d;

Bütün $(v, t o)$ kənarlarını iterasiya edin. Əgər $t o$ zirvəsi $v$ -nin valideyni deyilsə, $t o$ üçün dərinlik üzrə axtarış başladın. Mənbədən $t o$ -ya olan məsafə $d + 1$ olacaq.

  for (int to : g[v])
    if (to != p) dfs(to, d + 1, v);
}

Proqramın əsas hissəsi. Giriş verilənlərini oxuyun.

scanf("%d", &n);
g.resize(n + 1);
dist.resize(n + 1);

Yönsüz ağacı qurun.

for (i = 1; i < n; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  g[v].push_back(u);
}

$1$ -ci zirvədən bütün digər zirvələrə olan ən qısa məsafələri tapın. Bu zirvədən ən uzaq məsafədə olan zirvəni $a$ kimi qeyd edin.

dfs(1, 0, -1);
a = max_element(dist.begin(), dist.begin() + n + 1) – 
                dist.begin();

$a$ zirvəsindən bütün digər zirvələrə olan ən qısa məsafələri tapın. Bu zirvədən ən uzaqda olan zirvəni $b$ kimi qeyd edin.

dfs(a, 0,  -1);
b = max_element(dist.begin(), dist.begin() + n + 1) – 
                dist.begin();

Ağacın diametrini çap edin — yəni $a$ ilə $b$ arasındakı ən qısa məsafəni.

printf("%d\n", dist[b]);

İki dəfə dərinlik üzrə axtarış (DFS) etməklə ağacın diametrini tapırıq.

Ağac dövr olmayan birləşik qraf olduğuna görə, həm DFS, həm də BFS başlanğıc zirvədən bütün digər zirvələrə olan ən qısa məsafələri düzgün hesablayır.

$a$ və $b$ — bir-birindən ən uzaqda yerləşən iki zirvədir — yəni ağacın diametrini təyin edən zirvələrdir.

$a$ zirvəsindən bütün digər zirvələrə qədər olan ən qısa məsafələri $d i s t a$ massivində, $b$ zirvəsindən olan məsafələri isə $d i s t b$ massivində saxlayırıq.

Sonra, hər bir $i$ zirvəsi üçün digər zirvələrə qədər maksimal məsafə belə hesablanır:

max (d i s t a [i], d i s t b [i])

Nümunə

Misaldakı ağacı nəzərdən keçirək.

Ağacın diametri, məsələn, $2$ və $5$ zirvələri arasındakı yol ola bilər.

Girişdə verilən ağac $g$ qonşuluq siyahısı kimi saxlanılır.

$a$ və $b$ zirvələrindən olan ən qısa məsafələr müvafiq olaraq $d i s t a$ və $d i s t b$ massivlərində saxlanılır.

vector<vector<int>> g;
vector<int> dista, distb;

dfs funksiyası zirvə $v$ -dən başlayaraq dərinlik üzrə axtarış aparır.

$d$ parametri — mənbədən $v$ zirvəsinə qədər olan məsafəni göstərir;
nəticələr $d i s t$ massivində saxlanılır;
$p$ parametri — axtarış zamanı $v$ zirvəsinin valideyni.

void dfs(int v, int d, vector<int>& dist, int p = -1)
{

Mənbədən $v$ zirvəsinə qədər olan məsafəni $d i s t [v]$ dəyişənində saxla:

  dist[v] = d;

Bütün $(v, t o)$ kənarları üzrə dövr qur. Əgər $t o$ — $v$ zirvəsinin valideyni deyilsə, o zaman həmin $t o$ zirvəsi üçün dərinlik üzrə axtarış davam etdir:

  for (int to : g[v])
    if (to != p) dfs(to, d + 1, dist, v);
}

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

scanf("%d", &n);
g.resize(n + 1);
dista.resize(n + 1);
distb.resize(n + 1);

Yönsüz ağacı qururuq.

for (i = 1; i < n; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  g[v].push_back(u);
}

Zirvə $1$ -dən ən qısa məsafələri hesablayırıq. Ondan ən uzaqda yerləşən zirvə $a$ -dır.

dfs(1, 0, dista, -1);
a = max_element(dista.begin() + 1, dista.begin() + n + 1) - dista.begin();

Daha sonra, $a$ zirvəsindən ən qısa məsafələri hesablayırıq və $d i s t a$ massivində saxlayırıq. $a$ zirvəsindən ən uzaq olan zirvə $b$ olacaq. $a$ və $b$ arasındakı məsafə ağacın diametridir.

dfs(a, 0, dista, -1);
b = max_element(dista.begin() + 1, dista.begin() + n + 1) - dista.begin();

Sonra, $b$ zirvəsindən ən qısa məsafələri hesablayırıq və $d i s t b$ massivində saxlayırıq.

dfs(b, 0, distb, -1);

Hər bir $i$ zirvəsi üçün ondan ən uzaq zirvəyə olan məsafəni çap edirik.

for (i = 1; i <= n; i++)
  printf("%d ", max(dista[i], distb[i]));
printf("\n");

Python ilə reallaşdırma

Rekursiya yığını üçün limit artırılır.

import sys
sys.setrecursionlimit(1000000)

dfs funksiyası zirvə $v$ -dən başlayaraq dərinlik üzrə axtarış (DFS) yerinə yetirir.

$d$ parametri başlanğıc nöqtədən $v$ zirvəsinə olan ən qısa məsafəni göstərir.
Nəticələr $d i s t$ massivində saxlanılır.
$p$ parametri $v$ zirvəsinin DFS zamanı valideynini göstərir.

def dfs(v, d, dist, p = -1):

Başlanğıc nöqtədən $v$ zirvəsinə olan ən qısa məsafəni $d i s t [v]$ -də saxla.

  dist[v] = d

Bütün $(v, t o)$ kənarlarını nəzərdən keçirt. Əgər $t o$ $v$ -nin valideyni deyilsə, bu halda $t o$ zirvəsi üçün DFS çağır.

  for to in g[v]:
    if to != p:
      dfs(to, d + 1, dist, v)

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

n = int(input())
g = [[] for _ in range(n + 1)]
dista = [0] * (n + 1)
distb = [0] * (n + 1)

Yönsüz ağacı qurun.

for _ in range(n - 1):
  u, v = map(int, input().split())
  g[u].append(v)
  g[v].append(u)

Ən qısa məsafələri $1$ -ci zirvədən hesablayın. Ondan ən uzaqda yerləşən zirvə $a$ -dır.

dfs(1, 0, dista)
a = dista.index(max(dista[1:]))

Daha sonra $a$ zirvəsindən ən qısa məsafələri hesablayın və nəticələri $d i s t a$ massivində saxlayın. $a$ -dan ən uzaqda yerləşən zirvə $b$ -dir. $a$ və $b$ zirvələri arasındakı məsafə ağacın diametri olacaq.

dfs(a, 0, dista)
b = dista.index(max(dista[1:]))

Daha sonra $b$ zirvəsindən ən qısa məsafələri hesablayın və nəticələri $d i s t b$ massivində saxlayın.

dfs(b, 0, distb)

Hər bir $i$ zirvəsi üçün ondan ən uzaq zirvəyə olan məsafəni çap edin.

result = [max(dista[i], distb[i]) for i in range(1, n + 1)]
print(*result)

Romanın valideynləri ona $n$ zirvəli və $n - 1$ qəlpəli istiqamətsiz, əlaqəli və çəkili qraf hədiyyə etdilər. Roman bu qrafda bütün zirvə cütlükləri arasındakı yolların ümumi uzunluğunu tapmaq istəyir. Yolun uzunluğu onun daxilində olan qəlpələrin çəkilərinin cəmi kimi müəyyən olunur. Çünki $u$ zirvəsindən $v$ zirvəsinə olan yol ilə $v$ zirvəsindən $u$ zirvəsinə olan yol eyni sayılır, Roman onları bir yol kimi nəzərə alır və fərqləndirmir.

Giriş. İlk sətirdə bir tam ədəd $n (2 \leq n \leq 1 0^{5})$ — qrafdakı zirvələrin sayı verilir.

Növbəti $n - 1$ sətrin hər birində üç tam ədəd verilir: bir qəlpə ilə birləşdirilmiş iki zirvənin nömrələri (zirvələr $1$ -dən $n$ -ə qədər nömrələnmişdir) və həmin qəlpənin çəkisi.

Çıxış. Bütün fərqli zirvə cütləri arasında olan yolların ümumi uzunluğunu $1 0^{9}$ -a görə modul ilə verin.

Məsələyə keçid

Ağacın istənilən zirvəsindən başlayaraq dərinlik üzrə axtarış (DFS) aparın. $(u, v)$ çəkisi $w$ olan bir qəlpəni nəzərdən keçirək. Əgər $v$ zirvəsi kök olan altqrafda $c$ sayda zirvə varsa, o zaman bu qəlpənin bir tərəfində $c$ , digər tərəfində isə $n - c$ zirvə yerləşir. Bu halda $(u, v)$ qəlpəsi $c \cdot (n - c)$ sayda müxtəlif zirvə cütü arasında olan yollarda istifadə olunur. Deməli, bu qəlpənin cəmi uzunluğa töhfəsi $c \cdot (n - c) \cdot w$ olacaq. Sadəcə dərinlik üzrə axtarışla bütün qəlpələri keçərək onların bu şəkildə töhfələrini hesablamaq kifayətdir.

Nümunə

Nümunələrdə verilmiş qraflar aşağıdakı quruluşa malikdir:

İlk nümunədə qəlpələrin ümumi yol uzunluğuna verdiyi töhfəni araşdıraq.

$(1, 2)$ qəlpəsi (çəki $1$ ) aşağıdakı 2 yolda iştirak edir:

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

Bu qəlpənin ümumi cəmi töhfəsi $1 \cdot 2 \cdot 1 = 2$ .

$(1, 3)$ qəlpəsi (çəki $3$ ) aşağıdakı 2 yolda iştirak edir:

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

Bu qəlpənin ümumi cəmi töhfəsi $2 \cdot 1 \cdot 3 = 6$ .

Yolların ümumi uzunluğu $2 + 6 = 8$ .

İkinci nümunədə $(1, 2)$ qəlpəsinin (çəki $5$ ) töhfəsini hesablayın.

$2$ zirvəsi kök olan altqrafda $c = 4$ zirvə var (özünü də daxil olmaqla). Digər tərəfdə isə $n - c = 6 - 4 = 2$ zirvə var. Buna görə, $(1, 2)$ qəlpəsi $c \cdot (n - c) = 4 \cdot 2 = 8$ fərqli yolda iştirak edir.

Həqiqətən, bunlar aşağıdakı cütlərdir:

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

Bu qəlpənin ümumi uzunluğa verdiyi töhfə:

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

Modul dəyərini $MO D$ kimi təyin edin.

#define MOD 1000000000

Girişdə verilən çəkili qraf qonşuluq siyahısı $g$ şəklində saxlanılır.

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

dfs funksiyası $v$ zirvəsindən başlayaraq dərinlik üzrə axtarış aparır və $v$ zirvəsi kök olan altqrafdakı zirvələrin sayını qaytarır (özünü də daxil olmaqla). Bu cəmi $c n t$ dəyişənində saxlayırıq. Əvvəlcə $c n t = 1$ götürülür, çünki altqrafda artıq $v$ zirvəsi var.

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

$(v, t o)$ qəlpəsini və onun çəkisi $w$ -nu nəzərdən keçirək. $t o$ zirvəsi kök olan altqrafda $c$ sayda zirvə varsa, bu zaman qəlpənin bir tərəfində $c$ , digər tərəfində isə $n - c$ zirvə yerləşir. $(v, t o)$ qəlpəsi $c \cdot (n - c)$ sayda müxtəlif zirvə cütü arasında olan yollarda iştirak edir. Beləliklə, bu qəlpənin cəmi uzunluğa verdiyi töhfə:

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

Əsas proqram hissəsi. Giriş çəkili qrafı qonşuluq siyahısına oxuyun.

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

Dərinlik üzrə axtarışı $1$ -ci zirvədən başlayın. Qrafın zirvələri $1$ -dən $n$ -ə qədər nömrələnmişdir.

dfs(1);

Cavabı çap edin.

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

Java tətbiqi

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]; // yoxlanılmayan tip

    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 tətbiqi

Modul dəyərini $MO D$ kimi təyin edin.

MOD = 1000000000

dfs funksiyası $v$ qovşağından başlayaraq dərinlik üzrə axtarış (DFS) aparır və $v$ qovşağında köklənmiş altqrafda yerləşən qovşaqların sayını qaytarır (özünü də daxil olmaqla). Bu say $c n t$ dəyişəni ilə hesablanır. Başlanğıcda $c n t = 1$ qoyulur, çünki altqraf artıq $v$ qovşağını ehtiva edir.

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

$(v, t o)$ çəkili kənarını nəzərdən keçirək. Qoy $t o$ qovşağında köklənmiş altqrafda $c$ qovşaq olsun. Onda bu kənarın bir tərəfində $c$ , digər tərəfində isə $n - c$ qovşaq yerləşir. $(v, t o)$ kənarı $c \cdot (n - c)$ fərqli qovşaq cütlüyü arasında olan yolların tərkibində olur. Deməli, bu kənarın bütün yolların ümumi uzunluğuna qatqısı belə hesablanır:

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ş verilənlərini oxuyun.

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

Dərinlik üzrə axtarışı $1$ -ci qovşaqdan başlayın. Qrafın qovşaqları $1$ -dən $n$ -ə kimi nömrələnib.

dfs(1)

Cavabı çap edin.

print(res)

$co l or [i]$ massivi $i$ təpəsinin rəngini saxlayır. $s [i]$ çoxluğu $i$ təpəsinin altqrafında olan rəngləri toplayır.

İstiqamətli ağac qonşuluq siyahısı kimi $g$ massivində saxlanılır. $res [i]$ isə $i$ təpəsinin altqrafında neçə müxtəlif rəng olduğunu göstərir.

#define MAX 1000010
int color[MAX], res[MAX];
set<int> s[MAX];
vector<vector<int> > g;

dfs funksiyası dərinlik üzrə keçidi $v$ təpəsindən başlayaraq həyata keçirir.

void dfs(int v)
{

İlk olaraq, $v$ təpəsinin öz rəngi $s [v]$ çoxluğuna əlavə olunur.

  s[v].insert(color[v]);

Ağacın $(v, t o)$ istiqamətli kənarları üzrə iterasiya aparılır.

  for (int to : g[v])
  {
    dfs(to);

Hər $(v, t o)$ kənarı üçün $s [t o]$ çoxluğu $s [v]$ çoxluğuna birləşdirilir. Əgər $s [v]$ çoxluğu $s [t o]$ çoxluğundan kiçikdirsə, əvvəlcə onlar yer dəyişdirilir. Sonra isə $s [t o]$ çoxluğunun bütün elementləri $s [v]$ çoxluğuna əlavə olunur.

    if (s[v].size() < s[to].size()) s[v].swap(s[to]);
    s[v].insert(s[to].begin(), s[to].end());

$s [t o]$ çoxluğu təmizlənir — artıq ona ehtiyac yoxdur.

    s[to].clear();
  }

Bundan sonra, $res [v]$ dəyişəninə $s [v]$ çoxluğunun ölçüsü yazılır — bu da $v$ təpəsinin altqrafında olan müxtəlif rənglərin sayıdır.

  res[v] = s[v].size();
}

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

scanf("%d",&n);
g.resize(n+1);
for(i = 1; i <= n; i++)
{
  scanf("%d %d",&p,&c);
  g[p].push_back(i);
  color[i] = c;
}

Ağacın kökündən — yəni $0$ indeksli təpədən — dərinlik üzrə axtarışa başlayın.

dfs(0);

Cavabı çap edin.

for(i = 1; i <= n; i++)
  printf("%d ",res[i]);
printf("\n");

Mançester və Liverpul sakinləri uzun və yorucu iş həftəsindən sonra istirahət üçün meşəyə yollanırlar. Orada onlar $n$ təpədən ibarət olan və hər təpəsi $c$ mümkün rəngdən biri ilə boyanmış unikal bir ağacla qarşılaşırlar.

Darixmamaq üçün, onlar məntiqi bacarıqlarını sınamaq qərarına gəlirlər. Ağacın kökü $1$ təpəsidir. Hər bir təpə üçün, iştirakçılar eyni rəngə malik olan ən yaxın əcdadı tapmağa çalışırlar.

Giriş. Birinci sətdə iki tam ədəd $n$ və $c (1 \leq n, c \leq 1 0^{5})$ — ağacdakı təpələrin və mümkün rənglərin sayı verilir.

İkinci sət $n - 1$ ədəddən ibarətdir: bunların $i$ -cisi $(i + 1)$ -ci təpənin valideynini göstərir.

Üçüncü sət $n$ ədəddən ibarətdir — təpələrin rəngləri. Hər rəng $1$ ilə $c$ arasında olan bir tam ədəddir.

Çıxış. Bir sətrə $n$ tam ədəd yazın: hər bir təpə üçün, onunla eyni rəngə malik olan ən yaxın əcdadın nömrəsini çıxışa verin. Əgər belə bir təpə yoxdursa, çıxışa $- 1$ yazın.

Tapşırığı aç

Gəlin məsələnin sadələşdirilmiş versiyasını nəzərdən keçirək. Tutaq ki, ağacdakı bütün təpələr eyni rəngdədir. Boş bir stek (stack) yaradıb DFS (dərinlik üzrə axtarış) başladaq. Hər dəfə bir təpəyə daxil olanda onu stekə əlavə edirik. Təpə üzrə işləmə bitdikdə onu stekdən çıxarırıq. DFS tamamlandıqda stek yenidən boş olacaq.

Sual: Vertex $v$ -yə daxil olmamışdan əvvəl, yəni onu stekə atmadan bir an əvvəl, stekin yuxarısında nə olacaq?

İndi əsas məsələyə qayıdaq. $c$ sayda stek yaradın — hər rəng üçün bir stek (məsələn, steklərin massivindən istifadə edərək). Başlanğıcda bütün steklər boşdur. DFS-i kökdən ( $1$ təpəsi) başlayın. Rəngi $co l or$ olan $v$ təpəsi üçün aşağıdakı addımlar icra olunur:

Əgər $s [co l or]$ steki boş deyilsə, onun yuxarısında olan təpə vertex $v$ ilə eyni rəngə malik ən yaxın əcdaddır. Əgər stek boşdursa, belə bir əcdad yoxdur, və cavab $- 1$ olacaq.
$v$ təpəsini $s [co l or]$ stekinə əlavə edin.
Rekursiv olaraq vertex $v$ -nin bütün övladları üçün DFS tətbiq edin.
Vertex $v$ üzrə işləmə bitdikdən sonra onu $s [co l or]$ stekindən çıxarın.

DFS zamanı biz $v$ təpəsində olanda, steklər kökdən $v$ təpəsinə qədər olan unikal yolda yerləşən təpələrin rəngləri haqqında məlumat saxlayır. Xüsusilə, $s [co l or]$ steki bu yolda rəngi $co l or$ olan bütün təpələrin nömrələrini saxlayır. Bu təpələr DFS zamanı ziyarət olunma sırasına uyğun şəkildə stekə əlavə olunur.

Nümunə

DFS prosesi $5$ təpəsinə çatanda $c = 4$ stekdən ikisi (rəngləri $3$ və $4$ olanlara uyğun olanlar) boş olacaq.

Rəngi $1$ olan stek (1 nömrəli stek) $1$ təpəsini, rəngi $2$ olan stek (2 nömrəli stek) isə $3$ təpəsini saxlayacaq. Çünki $5$ təpəsinin rəngi $2$ -dir, onunla eyni rəngə malik ən yaxın əcdadı $2$ nömrəli stekin yuxarısındakı təpə olacaq.

Beləliklə, $5$ təpəsinin eyni rəngə malik ən yaxın əcdadı $3$ -dür.

Massivləri elan edin.

vector<int> col, res;
vector<vector<int> > g;
vector<stack<int> > s;

dfs funksiyası $v$ təpəsindən başlayaraq dərinlik üzrə axtarış aparır.

void dfs(int v)
{

$v$ təpəsinin rəngi $co l or$ dəyişənində saxlanılır.

  int color = col[v];

$v$ təpəsi ilə eyni rəngə malik ən yaxın əcdadın nömrəsi $res [v]$ dəyişənində saxlanılır.

  if(s[color].empty())
    res[v] = -1;
  else
    res[v] = s[color].top();

$v$ təpəsini onun rənginə uyğun olan stekə əlavə edin.

  s[color].push(v);

$v$ təpəsinin bütün övladlarını iterasiya edin və hər biri üçün rekursiv olaraq DFS tətbiq edin.

  for (int to : g[v])
    dfs(to);

$v$ təpəsinin emalı başa çatdıqdan sonra (yəni, ondan çıxış zamanı), onu rənginə uyğun olan stekdən çıxarın.

  s[color].pop();
}

Proqramın əsas hissəsi. Giriş verilənlərini oxuyun və ağacı qurun.

scanf("%d %d", &n, &c);
g.resize(n + 1);
for(i = 2; i <= n; i++)
{
  scanf("%d",&val);
  g[val].push_back(i);
}

Ağac təpələrinin rənglərini oxuyun.

col.resize(n + 1);
for(i = 1; i <= n; i++)
  scanf("%d",&col[i]);

DFS-i $1$ təpəsindən başladın.

s.resize(c + 1);
res.resize(n + 1);
dfs(1);

Cavabı çap edin.

for(i = 1; i <= n; i++)
  printf("%d ",res[i]);
printf("\n");

Python tətbiqi

Rekursiya üçün stek ölçüsünü artırın.

import sys
sys.setrecursionlimit(1000000)

dfs funksiyası $v$ təpəsindən başlayaraq dərinliyinə doğru axtarış (DFS) yerinə yetirir.

def dfs(v):

$v$ təpəsinin rəngi dəyişəndə $co l or$ dəyişənində saxlanılır.

  color = col[v]

$v$ təpəsi ilə eyni rəngdə olan ən yaxın ata təpənin nömrəsi $res [v]$ dəyişənində saxlanılır.

  if not s[color]:
    res[v] = -1
  else:
    res[v] = s[color][-1]

$v$ təpəsi öz rənginə uyğun olan stekə əlavə olunur.

  s[color].append(v)

$v$ təpəsinin bütün övladları üçün DFS rekursiv şəkildə çağırılır.

  for to in g[v]:
    dfs(to)

$v$ təpəsinin emalı başa çatdıqdan sonra, o, rənginə uyğun olan stekdən çıxarılır.

  s[color].pop()

Proqramın əsas hissəsi. Giriş verilənlərini oxuyun və ağacı qurun.

n, c = map(int, input().split())
lst = list(map(int, input().split()))
g = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
  val = lst[i - 2]
  g[val].append(i)

Ağacın təpələrinin rənglərini oxuyun.

col = [0] * (n + 1)
col[1:] = list(map(int, input().split()))

Dərinliyinə doğru axtarışı $1$ təpəsindən başlayın.

s = [[] for _ in range(c + 1)]
res = [0] * (n + 1)
dfs(1)

Cavabı çap edin.

print(*res[1:])

Boş vaxtlarında Farmer John öz video paylaşım platforması olan MooTube-u yaratdı. MooTube-da onun inəkləri videolar çəkə, paylaşa və kəşf edə bilərlər. İndiyə qədər inəklər $n$ video yükləmişlər, və bu videolar $1$ -dən $n$ -ə qədər nömrələnmişdir.

Lakin Farmer John inəklərinə yeni videolar tapmaqda necə kömək edəcəyini tam başa düşmür. O, hər video üçün "tövsiyə olunan videolar" siyahısı hazırlamaq istəyir — bu siyahı baxılmış videolara bənzərlik əsasında hazırlanacaq.

İki video arasında nə qədər bənzərlik olduğunu müəyyən etmək üçün John uyğunluq metrikası təqdim edir. O, əllə $n - 1$ video cütünü qiymətləndirir və hər cütə uyğunluq dəyəri təyin edir. Bu cütlərdən istifadə edərək, John videoların hər birini qrafın təpəsi kimi qəbul edib və uyğunluq dəyərləri olan kənarlarla birləşdirir.

Rahatlıq üçün John bu $n - 1$ cütü elə seçir ki, istənilən iki video arasında yalnız bir yol mövcud olsun — yəni, video şəbəkəsi bir ağac təşkil edir.

O, iki video arasındakı uyğunluğu, onları birləşdirən yol boyunca olan kənarların minimum uyğunluğu kimi müəyyənləşdirir.

İndi Farmer John $k$ dəyərini seçmək istəyir ki, MooTube-da olan istənilən video üçün uyğunluğu azı $k$ olan bütün digər videolar tövsiyə kimi göstərilsin. Lakin o qorxur ki, çoxlu tövsiyələr inəklərin süd verməsini dayandıra bilər, buna görə də o, müxtəlif $k$ dəyərləri üçün neçə video tövsiyə ediləcəyini dəqiq hesablamaq istəyir.

Farmer John sizə müraciət edir: sizə bir neçə sorğu verilir, hər biri $k$ dəyəri və bir video nömrəsindən ibarətdir. Hər sorğu üçün, əgər tövsiyə üçün tələb olunan minimum uyğunluq $k = k_{i}$ olsa, videoya neçə digər video tövsiyə olunacağını müəyyənləşdirməlisiniz.

Giriş. Birinci sətirdə iki tam ədəd $n$ və $q (1 \leq n, q \leq 5000)$ — video sayı və sorğuların sayı verilir.

Növbəti $n - 1$ sətirdə Farmer John tərəfindən qiymətləndirilmiş video cütləri verilir. Hər sətirdə üç tam ədəd $p_{i}, q_{i}$ və $r_{i} (1 \leq p_{i}, q_{i} \leq n, 1 \leq r_{i} \leq 1 0^{9})$ , bu o deməkdir ki, $p_{i}$ və $q_{i}$ videoları uyğunluq dəyəri $r_{i}$ olan kənarla birləşdirilmişdir.

Sonra isə $q$ sorğu verilir. $i$ -ci sorğuda iki tam ədəd $k_{i}$ və $v_{i} (1 \leq k_{i} \leq 1 0^{9}, 1 \leq v_{i} \leq n)$ verilir — bu o deməkdir ki, Farmer John soruşur: əgər minimum uyğunluq $k = k_{i}$ olarsa, $v_{i}$ videosu üçün neçə video tövsiyə ediləcək?

Çıxış. $q$ sətir çap edin. $i$ -ci sətirdə Farmer John-un $i$ -ci sorğusunun cavabını verin.

Nümunə. Farmer John videolar arasında aşağıdakı əlaqələri qurmuşdur:

Video $1$ və video $2$ arasında uyğunluq $3$ -dür,
Video $2$ və video $3$ arasında uyğunluq $2$ -dir,
Video $2$ və video $4$ arasında uyğunluq $4$ -dür.

Bu məlumatlara əsasən, digər video cütləri arasındakı uyğunluqları hesablaya bilərik:

Video $1$ və video $3$ : uyğunluq = $min (3, 2) = 2$ ,
Video $1$ və video $4$ : uyğunluq = $min (3, 4) = 3$ ,
Video $3$ və video $4$ : uyğunluq = $min (2, 4) = 2$ .

İndi isə aşağıdakı sorğular üçün hansı videoların tövsiyə olunacağını nəzərdən keçirək:

Video $2$ üçün $k = 1$ olduqda, videolar $1$ , $3$ və $4$ tövsiyə olunacaq.
Video $1$ üçün $k = 3$ olduqda, videolar $2$ və $4$ tövsiyə olunacaq.
Video $1$ üçün $k = 4$ olduqda, heç bir video tövsiyə olunmayacaq.

Problemi aç

Hər bir $(k_{i}, v_{i})$ sorğusu üçün $v_{i}$ təpəsindən başlayaraq DFS və ya BFS həyata keçirin. Axtarış zamanı yalnız uyğunluğu $k_{i}$ və ya ondan böyük olan kənarları keçin.

Əldə edilə bilən təpələrin sayını $res$ kimi hesablayın, başlanğıc təpə $v_{i}$ nəzərə alınmadan. $res$ dəyəri $(k_{i}, v_{i})$ sorğusunun cavabıdır.

Nümunə

Farmer John videolar arasında aşağıdakı əlaqələri qurmuşdur:

Video $1$ və video $2$ arasında uyğunluq $3$ -dür,
Video $2$ və video $3$ arasında uyğunluq $2$ -dir,
Video $2$ və video $4$ arasında uyğunluq $4$ -dür.

Bu məlumatlara əsaslanaraq digər video cütləri arasındakı uyğunluğu hesablaya bilərik:

Video $1$ və video $3$ : uyğunluq = $min (3, 2) = 2$ ,
Video $1$ və video $4$ : uyğunluq = $min (3, 4) = 3$ ,
Video $3$ və video $4$ : uyğunluq = $min (2, 4) = 2$ .

İndi aşağıdakı sorğular üçün hansı videoların tövsiyə olunacağını baxaq:

$k = 1$ üçün video $2$ -dən: videolar $1$ , $3$ və $4$ tövsiyə olunur.
$k = 3$ üçün video $1$ -dən: videolar $2$ və $4$ tövsiyə olunur.
$k = 4$ üçün video $1$ -dən: heç bir video tövsiyə olunmur.

Girişi verilən qrafı qonşuluq siyahısı $g$ şəklində saxlayın.

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

bfs funksiyası başlanğıc təpədən ( $s t a r t$ ) genişlik üzrə axtarış aparır və başlanğıc təpə istisna olmaqla ziyarət olunan təpələrin sayını qaytarır. Axtarış zamanı yalnız çəkisi ən az $k$ olan kənarlarla hərəkət edilir.

int bfs(int start, int k)
{

Bu məsələdə məsafə massivinə ehtiyac yoxdur — yalnız təpənin ziyarət olunub-olunmadığını izləmək kifayətdir. Əgər $i$ təpəsi ziyarət olunubsa, $u se d [i] = 1$ təyin olunur.

  vector<int> used(n + 1);
  used[start] = 1;

Bir növbə yaradılır və başlanğıc təpə $s t a r t$ ora əlavə olunur.

  queue<int> q;
  q.push(start);

Nəticə dəyişəni $res$ ziyarət olunan təpələrin (başlanğıc təpədən başqa) sayını saxlayır.

  int res = 0;

Genişlik üzrə axtarış başlayır.

  while (!q.empty())
  {

Növbədən təpə $v$ çıxarılır.

    int v = q.front(); q.pop();

Bütün $v$ təpəsinə bitişik kənarlar üzrə iterasiya aparılır.

    for (auto edge : g[v])
    {

$(v, t o)$ kənarını və onun çəkisini ( $k t o$ ) götür.

     int to = edge.first;
     int kto = edge.second;

Əgər kənarın çəkisi $k t o < k$ olarsa, bu kənar atlanır (bu kənarla hərəkət qadağandır).

      if (kto < k) continue;

Əgər $t o$ təpəsi hələ ziyarət olunmayıbsa, onu növbəyə əlavə et, ziyarət olunmuş kimi işarələ və $res$ sayğacını $1$ artır.

      if (used[to] == 0)
      {
        q.push(to);
        used[to] = 1;
        res++;
      }
    }
  }

Sorğunun cavabını qaytar.

  return res;
}

Əsas proqram hissəsi. Giriş məlumatlarını oxu.

scanf("%d %d", &n, &qu);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d %d", &p, &q, &r);

$(p, q)$ kənarını çəkisi $r$ olmaqla yönsüz şəkildə qonşuluq siyahısına əlavə et.

  g[p].push_back({ q, r });
  g[q].push_back({ p, r });
}

$q u$ sorğularını bir-bir emal et.

while (qu--)
{
  scanf("%d %d", &k, &v);

Təpə $v$ -dən başlayaraq eninə doğru axtarış (BFS) həyata keçirin və bu zaman ziyarət olunan təpələrin sayını çap edin.

  printf("%d\n", bfs(v, k));
}

Alqoritmin reallaşdırılması — dərinlik üzrə axtarış (DFS)

Girişi verilmiş qraf qonşuluq siyahısı $g$ kimi saxlanılır.

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

dfs funksiyası $v$ təpəsindən başlayaraq dərinlik üzrə axtarış həyata keçirir və ziyarət olunan təpələrin sayını qaytarır. Axtarış zamanı yalnız çəkisi $k$ və ya ondan böyük olan kənarlarla hərəkət etmək icazəlidir.

int dfs(int v, int k)
{

$v$ təpəsini ziyarət olunmuş kimi işarələ.

  used[v] = 1;

$v$ təpəsindən başlayan altqrafda ziyarət olunan təpələrin sayı $res$ dəyişənində saxlanılır.

  int res = 1;

$v$ təpəsinə bitişik bütün kənarları dövr ilə yoxla.

  for (auto edge : g[v])
  {

$(v, t o)$ kənarını və onun çəkisini $k t o$ götür.

    int to = edge.first;
    int kto = edge.second;

Əgər $k t o < k$ olarsa, bu kənar atlanır (bu kənarla hərəkət qadağandır).

    if (kto < k) continue;

Əgər $t o$ təpəsi hələ ziyarət olunmayıbsa, $t o$ təpəsindən DFS başlat və nəticəni $res$ dəyişəninə əlavə et.

    if (used[to] == 0)
      res += dfs(to, k);
  }
  return res;
}

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

scanf("%d %d", &n, &qu);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d %d", &p, &q, &r);

Çəkisi $r$ olan $(p, q)$ istiqamətsiz kənarını qonşuluq siyahısına əlavə et.

  g[p].push_back({ q, r });
  g[q].push_back({ p, r });
}

$q u$ sorğularını bir-bir emal et.

while (qu--)
{
  scanf("%d %d", &k, &v);

$v$ təpəsindən başlayaraq dərinlik üzrə axtarış həyata keçir. Axtarış zamanı ziyarət olunan təpələrin sayını çap et, başlanğıc təpə $v$ daxil edilmədən.

  used.assign(n + 1, 0);
  printf("%d\n", dfs(v, k) - 1);
}

Dərinlik üzrə axtarış (DFS) istifadə edərək, $1$ təpəsi ilə bütün digər təpələr arasındakı XOR cəmlərini hesablayın. $1$ və $v$ təpələri arasındakı XOR cəmini $x [v]$ massivində saxlayın. $x$ massivində neçə $1$ olduğunu $o n es$ , neçə $0$ olduğunu isə $zeroes$ kimi təyin edək ( $o n es + zeroes = n$ ). O zaman cavab $o n es \cdot zeroes$ olacaq.

Nümunə

Nümunədə verilmiş qrafı nəzərdən keçirək.

Hər təpənin yanında $1$ ilə həmin təpə arasındakı XOR cəmi $x [v]$ göstərilib. Əgər bəzi $v$ və $u$ təpələri üçün $x [v] = x [u]$ olarsa, o zaman bu iki təpə arasında XOR cəmi $0$ olacaq və bu cütlük ümumi cəmə töhfə verməyəcək. Əgər $x [v] \neq = x [u]$ olarsa, bu cüt XOR cəminə $1$ töhfə verəcək.

Beləliklə, cavab $x [v] \neq = x [u]$ olan bütün cütlüklərin sayına bərabərdir. Bu say $o n es \cdot zeroes = 2 \cdot 3 = 6$ olacaq. XOR cəminə $1$ töhfə verən cütlüklər bunlardır: $(1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (4, 5)$ .

Girişi qonşuluq siyahısı $g$ şəklində saxlayın. $x$ massivini elan edin.

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

dfs funksiyası dərinlik üzrə axtarış həyata keçirir və $1$ və $v$ təpələri arasındakı XOR cəmi $x [v]$ massivində saxlanılır. Hal-hazırkı XOR cəmi $c u r_x or$ , $v$ təpəsinin valideyni isə $p$ ilə göstərilir.

void dfs(int v, int cur_xor, int p = -1)
{
  x[v] = cur_xor;
  for (auto z : g[v])
  {
    int to = z.first;
    int w = z.second;
    if (to != p) dfs(to, cur_xor ^ w, v);
  }
}

Proqramın əsas hissəsi. Giriş qrafını oxuyun.

scanf("%d", &n);
g.resize(n + 1);
x.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});
}

Dərinlik üzrə axtarışı $1$ təpəsindən başlayın.

dfs(1, 0, -1);

$x$ massivində $zeroes$ və $o n es$ sayını hesablayın.

ones = 0;
for (i = 1; i <= n; i++)
  if (x[i] == 1) ones++;
zeroes = n - ones;

Cavabı ekrana verin.

printf("%lld\n", 1LL * ones * zeroes);

Python reallaşdırması

dfs funksiyası $1$ və $v$ təpələri arasındakı XOR cəmini hesablayan dərinlik üzrə axtarış həyata keçirir. $1$ və $v$ arasındakı cari XOR cəmi $c u r_x or$ ilə göstərilir. $v$ təpəsinin valideyni $p$ -dir.

def dfs(v, cur_xor = 0, p = -1):
  x[v] = cur_xor
  for to, w in g[v]:
    if to != p:
      dfs(to, cur_xor ^ w, v)

Proqramın əsas hissəsi. Girişi oxuyun.

n = int(input())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
  u, v, d = map(int, input().split())
  g[u].append((v, d))
  g[v].append((u, d))

$x$ massivini başlat.

x = [0] * (n + 1)

Dərinlik üzrə axtarışı təpə $1$ -dən başlayın.

dfs(1)

$x$ massivindəki $zeroes$ və $o n es$ sayını hesablayın.

ones = sum(x)
zeroes = n - ones

Cavabı ekrana verin.

print(ones * zeroes)

$1$ -dən $n$ -ə qədər nömrələnmiş $n$ təpədən ibarət bir ağac verilir. Ağacdakı $i$ -ci kənar $a_{i}$ və $b_{i}$ təpələrini birləşdirir. $i$ -ci təpə $c_{i}$ rəngi ilə boyanıb (bu məsələdə rənglər tam ədədlərlə təmsil olunur).

Bir təpə $x$ yaxşı hesab olunur əgər təpə $1$ -dən təpə $x$ -ə qədər olan ən qısa yol üzərində $x$ -dən başqa elə bir təpə yoxdur ki, $x$ ilə eyni rəngdə olsun.

Bütün yaxşı təpələri tapın.

Giriş. Birinci sətirdə bir tam ədəd $n (2 \leq n \leq 1 0^{5})$ — təpələrin sayı verilir.

İkinci sətirdə $n$ tam ədəd verilir — təpələrin rəngləri: $c_{1}, c_{2}, \dots, c_{n} (1 \leq c_{i} \leq 1 0^{5})$ .

Növbəti $n - 1$ sətrin hər birində iki tam ədəd $a_{i}$ və $b_{i} (1 \leq a_{i}, b_{i} \leq n)$ verilir — ağacdakı kənarlar.

Çıxış. Bütün yaxşı təpələrin nömrələrini artan sıra ilə, hər sətrə biri olmaqla çap edin.

Məsələyə keçid

Təpə $1$ -dən başlayaraq dərinlikə doğru axtarış (DFS) həyata keçirin. Rəngi $co l or [v]$ olan $v$ təpəsinə daxil olduqda, $u se d [co l or [v]]$ dəyişəninin dəyərini $1$ vahid artırın. $u se d [co l or [v]]$ dəyəri, $1$ təpəsindən $v$ təpəsinə qədər (daxil olmaqla) olan yolda bu rəngin neçə dəfə göründüyünü göstərir. Əgər bu rəng yolda yalnız bir dəfə görünürsə, $v$ təpəsi "yaxşı" hesab olunur və nəticə çoxluğuna əlavə olunur.

Təpədən çıxarkən $u se d [co l or [v]]$ dəyişəninin dəyərini $1$ vahid azaldın.

Nümunə

Birinci nümunədəki qraf aşağıdakı kimidir:

Təpə $5$ "yaxşı" deyil, çünki $1 - 2 - 5$ yolunda həm $1$ , həm də $5$ təpələri eyni rəngdədir.

Təpə $6$ isə "yaxşı"dır, çünki $1 - 2 - 3 - 6$ yolunda ara təpələrin heç biri $6$ ilə eyni rəngə malik deyil.

Giriş qrafını qonşuluq siyahısı ( $g$ ) kimi saxlayın. Aşağıdakı massivləri elan edin:

vector<int> used, color;
vector<vector<int>> g;
set<int> st;

dfs funksiyası dərinliyə doğru axtarışı həyata keçirir. $p a r$ dəyişəni $v$ təpəsinin valideynidir.

void dfs(int v, int par)
{

Təpə $v$ -nin rəngi $co l or [v]$ -dir. Bu rəngin yolda göründüyünü qeyd edin:

  used[color[v]]++;

Əgər $co l or [v]$ rəngi yolda yalnız bir dəfə görünürsə, $v$ təpəsini nəticə çoxluğuna əlavə edin:

  if (used[color[v]] == 1) st.insert(v);

Təpə $v$ -dən çıxan bütün $(v, t o)$ kənarları üzrə iterasiya aparın. Əgər $t o$ təpəsi $v$ -nin valideyni deyilsə $(t o \neq = p a r)$ , ondan dərinliyə doğru axtarışa başlayın. Bu halda $t o$ -nun valideyni $v$ olur.

  for (int to : g[v])
    if (to != par) dfs(to, v);

Təpə $v$ -dən çıxarkən, $u se d [co l or [v]]$ dəyərini $1$ vahid azaldın.

  used[color[v]]--;
}

Proqramın əsas hissəsi. Təpələrin sayını $n$ və rənglər massivini oxuyun.

scanf("%d", &n);
color.resize(n + 1);
for (i = 1; i <= n; i++)
  scanf("%d", &color[i]);

Qrafı oxuyun.

used.resize(100001);
g.resize(n + 1);
for (i = 1; i < n; i++)
{
  scanf("%d %d", &x, &y);
  g[x].push_back(y);
  g[y].push_back(x);
}

Təpə $1$ -dən dərinlik üzrə axtarışa başlayın.

dfs(1, 1);

Yaxşı təpələri çap edin. Onlar $s t$ çoxluğunda saxlanılır.

for (int val : st)
  printf("%d\n", val);

$1$ -dən $n$ -ə qədər nömrələnmiş $n$ təpə və $n - 1$ kənardan ibarət bir ağac verilir. $i$ -ci kənar $a_{i}$ və $b_{i}$ təpələrini birləşdirir.

Sizin ixtiyarınızda $k$ rəng var. Ağacın hər təpəsini bu $k$ rəngdən biri ilə rəngləməlisiniz, aşağıdakı şərti ödəməklə:

Əgər iki fərqli təpə $x$ və $y$ arasında olan məsafə $2$ və ya daha azdırsa, o zaman $x$ və $y$ fərqli rənglərə malik olmalıdır.

Ağacı bu şərti pozmadan neçə fərqli şəkildə rəngləmək olar? Cavabı $1 0^{9} + 7$ modulu üzrə hesablayın.

Giriş. Birinci sətirdə iki tam ədəd $n$ və $k (1 \leq n, k \leq 1 0^{5})$ verilir. Növbəti $n - 1$ sətrin hər birində iki tam ədəd $a_{i}$ və $b_{i} (1 \leq a_{i}, b_{i} \leq n)$ — ağacın kənarları verilir.

Çıxış. Ağacı verilmiş qayda ilə neçə müxtəlif şəkildə rəngləmək olar? Cavabı $1 0^{9} + 7$ modulu üzrə çap edin.

Açıq məsələ

Rəngləməyə təpə $1$ -dən başlayaq. Bu təpə $k$ fərqli rənglə rənglənə bilər.

Tutaq ki, biz $v$ təpəsindəyik. Əgər onun valideyni yoxdursa ( $v = 1$ ), onun övladları $k - 1$ fərqli rənglə rənglənə bilər. Əgər $v$ -nin valideyni varsa, o zaman övladları $k - 2$ fərqli rənglə rənglənə bilər. Çünki $v$ -nin övladlarının arasındakı məsafə $2$ -ə bərabərdir və bu səbəbdən onlar eyni rəngdə ola bilməzlər.

Əgər $v$ -nin valideyni varsa, o zaman onun birinci övladı $k - 2$ , ikinci övladı $k - 3$ və s. şəkildə rənglənə bilər.

Sadəcə olaraq, hər bir təpə üçün istifadə oluna biləcək rənglərin sayını bir-birinə vurmaq qalır.

Nümunə

Birinci nümunədə ağacı rəngləmək üçün $6$ fərqli yol mövcuddur:

İkinci testi nəzərdən keçirək. Hər bir təpənin üzərinə onun neçə fərqli rənglə rənglənə biləcəyini yazaq. Məsələn, $5$ təpəsi yalnız $2$ rənglə rənglənə bilər, çünki onun rəngi $1$ və $4$ təpələrinin rəngindən fərqli olmalıdır. Ağacı rəngləməyin ümumi yolları

Girişi təmsil edən qrafı qonşuluq siyahısı $g$ şəklində yadda saxlayın. Modul üçün sabit $MO D$ təyin edin.

#define MOD 1000000007
vector<vector<int>> g;

dfs funksiyası $v$ təpəsi ilə köklənmiş ağacı $MO D = 1 0^{9} + 7$ modulu üzrə neçə yolla rəngləmək mümkün olduğunu qaytarır. $v$ təpəsinin valideyni $p$ , özü isə $co l$ rənglə rənglənə bilər.

int dfs(int v, int col, int p = -1)
{
  long long res = col;

Hazırda $v$ təpəsindəyik. $c n t$ dəyişənində $v$ təpəsinin övladları üçün istifadə oluna bilməyəcək rənglərin sayı saxlanılır. Başlanğıcda $c n t = 1$ təyin edilir, çünki övladlar $v$ -nin rəngini ala bilməzlər. Əgər $v$ -nin valideyni varsa ( $p \neq = - 1$ ), o zaman övladlar həmçinin valideynin rəngini də ala bilməz.

  int cnt = 1;
  if (p >= 0) cnt++;

$v$ təpəsinin bütün övladları $t o$ üzrə iterasiya aparılır.

  for (int to : g[v])
    if (to != p)
    {

$t o$ təpəsi $k - c n t$ fərqli rənglə rənglənə bilər. Hər bir övladdan sonra $c n t$ dəyişəni $1$ vahid artır.

      res = (res * dfs(to, k - cnt, v)) % MOD;
      cnt++;
    }
  return res;
}

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

scanf("%d %d", &n, &k);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  g[b].push_back(a);
}

Dərinlik üzrə axtarışı təpə $1$ -dən başladın. $1$ nömrəli təpə $k$ rəngdən biri ilə rənglənə bilər.

res = dfs(1, k);

Cavabı çap edin.

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

Python reallaşdırılması

Python interpretatorunun yığın dərinliyini müəyyən olunmuş həddə qədər artırın.

import sys
sys.setrecursionlimit(1000000)

Modul üçün sabit $MO D$ təyin edin.

MOD = 1000000007

dfs funksiyası $v$ təpəsi ilə köklənmiş ağacı $MO D = 1 0^{9} + 7$ modulu üzrə neçə yolla rəngləmək mümkün olduğunu qaytarır. $v$ təpəsinin valideyni $p$ -dir. $v$ təpəsi $co l$ qədər fərqli rənglə rənglənə bilər.

def dfs(v, col, p = -1):
  res = col

Hazırda $v$ təpəsindəyik. $c n t$ dəyişənində $v$ təpəsinin övladları üçün istifadə oluna bilməyəcək rənglərin sayı saxlanılır. Başlanğıcda $c n t = 1$ təyin edilir, çünki övladlar $v$ təpəsinin rəngini ala bilməzlər. Əgər $v$ təpəsinin valideyni varsa ( $p \neq = - 1$ ), o zaman övladlar həmçinin valideynin rəngini də ala bilməzlər.

  cnt = 1
  if p >= 0: cnt += 1

$v$ təpəsinin bütün övladları $t o$ üzrə iterasiya aparılır.

  for to in g[v]:
    if to != p:

$t o$ təpəsi $k - c n t$ fərqli rənglə rənglənə bilər. Hər bir övladdan sonra $c n t$ dəyişəni $1$ vahid artır.

      res = (res * dfs(to, k - cnt, v)) % MOD
      cnt += 1
  return res

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

n, k = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)

Dərinlik üzrə axtarışı təpə $1$ -dən başladın. $1$ nömrəli təpə $k$ rəngdən biri ilə rənglənə bilər.

res = dfs(1, k)

Cavabı çap edin.

print(res)

Ölkədə $n$ şəhər və $n - 1$ ikitərəfli yol var. Elədir ki, yalnız bu yollardan istifadə etməklə istənilən şəhərdən digərinə getmək mümkündür. Şəhərlər $1$ -dən $n$ -ə qədər nömrələnmişdir.

Başlanğıcda, bütün yollar pis vəziyyətdə hesab olunur, lakin hökumət bu yollardan bəzilərini yaxşılaşdırmağı planlaşdırır. Vətəndaşlar təkmilləşdirmələrdən yalnız o zaman razı qalacaqlar ki, paytaxtdan (yəni $1$ -ci şəhərdən) istənilən digər şəhərə gedən yolda ən çox bir pis vəziyyətdə yol olsun.

Tələbi ödəmək üçün yolların bəzilərini yaxşılaşdırmağın neçə mümkün üsulu olduğunu müəyyən edin. Cavab çox böyük ola biləcəyindən onu $1 0^{9} + 7$ modulu üzrə çap edin.

Giriş. Birinci sətirdə bir tam ədəd $n (2 \leq n \leq 2 \cdot 1 0^{5})$ — ölkədəki şəhərlərin sayı verilir. İkinci sətirdə $n - 1$ ədəd $p_{2}, p_{3}, p_{4}, \dots, p_{n} (1 \leq p_{i} \leq i - 1)$ ədədləri verilir. Burada $p_{i}$ ədədi $p_{i}$ və $i$ şəhərləri arasında bir yolun olduğunu bildirir.

Çıxış. Yolları yaxşılaşdırmağın tələbə uyğun gələn bütün mümkün yollarının sayını $1 0^{9} + 7$ modulu üzrə çap edin.

Problemi aç

$q (v)$ — $v$ təpəsi ilə köklənmiş altqraf üçün yolları yaxşılaşdırmağın üsullarının sayını göstərsin. $t o$ — $v$ təpəsinin övladıdır.

Əgər $(v, t o)$ yolu pis vəziyyətdə qalırsa, o zaman $t o$ təpəsinin altqrafındakı bütün yollar yaxşılaşdırılmalıdır.
Əgər $(v, t o)$ yolu yaxşılaşdırılırsa, o zaman $t o$ təpəsinin altqrafı üçün yolları yaxşılaşdırmağın sayı $q (t o)$ -ya bərabərdir.

Əgər $t o_{1}, t o_{2}, ..., t o_{k}$ — $v$ təpəsinin övladlarıdırsa, o zaman

q (v) = (q (t o_{1}) + 1) \cdot (q (t o_{2}) + 1) \cdot \dots \cdot (q (t o_{k}) + 1)

Əgər $v$ yarpaq təpədirsə (övladı yoxdursa), onda $q (v) = 1$ qəbul edilir.

Nümunə

Məsələdə verilmiş nümunələrə baxaq. Hər təpə üçün $f (v)$ qiymətini qeyd edək.

Birinci nümunədə yolları elə yaxşılaşdırmağın $4$ üsulu var ki, şəhər $1$ -dən istənilən digər şəhərə qədər yolda ən çox bir pis vəziyyətdə yol olsun. Pis vəziyyətdə olan yollar kəsik xətlərlə, yaxşılaşdırılmış yollar isə bərk xətlərlə göstərilib.

Bütün hesablamalar $MO D = 1 0^{9} + 7$ moduluna görə aparılır.

#define MOD 1000000007

dfs funksiyası $f (v)$ qiymətini hesablayır — $v$ təpəsindən başlayan altqraf üçün yolları yaxşılaşdırmağın üsullarının sayı. $v$ təpəsinin valideyni $p$ -dir.

long long dfs(int v, int p = -1)
{
  long long s = 1;

Əgər $t o_{1}, t o_{2}, ..., t o_{k}$ — $v$ təpəsinin övladlarıdırsa, o zaman

f (v) = (f (t o_{1}) + 1) \cdot (f (t o_{2}) + 1) \cdot \dots \cdot (f (t o_{k}) + 1)

  for (int to : g[v])
    if (to != p)
    {
      long long sub = dfs(to, v);
      s = (s * (sub + 1)) % MOD;
    }
  return s;
}

Giriş məlumatlarını oxuyun və ağacı qurun.

scanf("%d", &n);
g.resize(n + 1);
for (i = 2; i <= n; i++)
{
  scanf("%d", &p);
  g[i].push_back(p);
  g[p].push_back(i);
}

Nəticəni hesablayın və çap edin.

res = dfs(1);
printf("%lld\n", res);

Aydın yay günlərində Nyuşa təmiz havada kəpənək tutmağı sevir. Amma bu gün o, xüsusilə hiyləgər bir kəpənəklə qarşılaşdı — kəpənək labirintə uçaraq orada gizlənməyə çalışdı.

Labirint $n$ otaqdan ibarətdir və bu otaqların bəziləri dəhlizlərlə birləşdirilib. Məlumdur ki, istənilən iki otaq arasında yalnız bir sadə yol mövcuddur və bu yol yalnız dəhlizlərdən keçir. Başqa sözlə, labirint $n$ təpə və $n - 1$ qırıqdan ibarət bir ağacdır.

Labirintin girişi $1$ -ci otaqdadır. Bir otaq yalnız bir başqa otaqla birləşibsə və bu otaq kök deyilsə (yəni $1$ -ci otaq deyilsə), o zaman bu otaq yarpaq hesab olunur. Hər yarpaq otaqda labirintdən çıxış mövcuddur. Kəpənək öz uçuşuna $1$ -ci otaqdan başlayır və hansısa çıxışa doğru hərəkət edir. O, sabit sürətlə hərəkət edir, heç vaxt geri dönmür və hər dəqiqədə bir dəhlizdən keçərək qonşu otağa keçir. Bütün dəhlizlər eyni uzunluqdadır.

Kəpənəyi tutmaq üçün Nyuşa dostlarının köməyinə müraciət etmək qərarına gəldi. Başlanğıcda hər biri istənilən çıxışı olan otaqda yerləşə bilər. Kəpənək çıxışlardan birinə doğru hərəkət etməyə başladığı anda dostlar da dərhal hərəkətə keçə bilərlər. Onlar da kəpənəklə eyni sürətlə hərəkət edirlər. Əgər onlardan biri kəpənəklə eyni otaqda və ya bir dəhlizin ortasında qarşılaşarsa, kəpənək tutulmuş sayılır. Əgər kəpənək heç bir dostla qarşılaşmadan çıxışa çatsa, azad olur.

Nyuşaya kömək edin — istənilən çıxış seçimi üçün kəpənəyin tutulacağına zəmanət verən minimum dost sayını müəyyən edin.

Giriş. İlk sətirdə bir tam ədəd $n (2 \leq n \leq 200000)$ — labirintdəki otaqların sayı verilir.

Növbəti $n - 1$ sətirin hər birində iki tam ədəd $u$ və $v (1 \leq u, v \leq n, u \neq = v)$ verilir — dəhlizlə birləşdirilmiş otaqların nömrələri.

Zəmanət verilir ki, verilmiş dəhliz sistemi bir ağac təşkil edir.

Çıxış. Tək bir tam ədəd çap edin — kəpənəyin tutulmasına zəmanət vermək üçün lazım olan minimum dostların sayı.

Problemi aç

Birinci təpədən başlayaraq dərinlik üzrə ilk keçid (DFS) yerinə yetirin. Hər bir təpə üçün iki qiymət hesablayın:

$d [v]$ — təpə $1$ -dən təpə $v$ -yə olan məsafə. Əgər $p$ təpə $v$ -nin valideynidirsə, onda
$d [v] = d [p] + 1$
$h [v]$ — təpə $v$ -dən öz altqrafında yerləşən ən yaxın yarpaq təpəyə olan məsafə. Əgər $t o_{1}, t o_{2}, ..., t o_{k}$ — $v$ təpəsinin övladlarıdırsa, onda
$h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])$
Əgər $v$ ağacın yarpaq təpəsidirsə, o zaman $h [v] = 0$ təyin edin.

Sonra ikinci DFS keçidi edin. Bu keçid zamanı $res [v]$ qiymətini hesablayın — əgər kəpənək bu altqrafa daxil olarsa, onu tutmaq üçün $v$ təpəsinin altqrafındakı yarpaqlarda yerləşdirilməli olan dostların minimal sayı.

Əgər $h [v] \leq d [v]$ , onda $res [v] = 1$ . Bu halda $v$ altqrafında ən yaxın dərinlikdə yerləşən yarpaq təpəyə bir dost yerləşdirmək kifayətdir: bu dost kəpənək kökdən gələnə qədər $v$ təpəsinə çatacaq.

Əks halda, əgər $t o_{1}, t o_{2}, ..., t o_{k}$ — $v$ təpəsinin övladlarıdırsa, onda

res [v] = res [t o_{1}] + res [t o_{2}] + ... + res [t o_{k}]

Əgər kəpənək $v$ təpəsində tutulmayıbsa, onu $v$ övladlarının altqraflarında tutmaq üçün hazır olmalıyıq.

Problemin son cavabı $res [1]$ olacaq.

Nümunə

Birinci nümunədə (soldakı diaqramda göstərilmişdir) iki dost tələb olunur və onlar çıxışlarda yerləşdirilməlidirlər. Kəpənək $1$ -ci təpədən ya $2$ -yə, ya da $3$ -ə uça bilər. Hər iki halda dostlardan biri onu qarşılayacaq.

İkinci nümunədə (sağdakı diaqramda) bir dost kifayətdir, hansı ki ya $3$ , ya da $4$ təpəsində yerləşə bilər. Kəpənək bir dəqiqədə $1$ -dən $2$ -yə uçar, həmin vaxtda dost da $2$ -yə çataraq onu tutur.

Növbəti nümunəyə baxaq.

Bu halda Nyuşaya kəpənəyi tutmaq üçün üç dost lazım olacaq.

Sonsuzluq sabitini və massivləri təyin edin.

#define INF 2000000000
vector<vector<int>> g;
vector<int> d, h, res;

dfs $(v, p, c n t)$ funksiyası təpə $v$ -dən başlayaraq dərinlik üzrə ilk keçidi (DFS) yerinə yetirir və $h [v]$ qiymətini qaytarır. Burada $p$ təpə $v$ -nin valideyni, $c n t$ isə təpə $1$ -dən $v$ -yə olan məsafəni göstərir. Keçid zamanı hər bir $v$ təpəsi üçün $d [v]$ və $h [v]$ qiymətləri hesablanır.

int dfs(int v, int p = -1, int cnt = 0)
{

$c n t$ dəyişəni, yəni $1$ -dən $v$ -yə olan məsafə, $d [v]$ -də saxlanılır.

  d[v] = cnt;
  int height = INF;

Təpə $v$ -nin bütün övladlarını keçin. $v \to t o$ qırağını nəzərdən keçirin. Əgər $t o = p$ -dirsə, bu halda keçidi atlayın.

  for (int to : g[v])
    if (to != p)

$h e i g h t$ dəyişənində aşağıdakı qiymət hesablanır:

min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}]),

burada $t o_{1}, t o_{2}, ..., t o_{k}$ təpə $v$ -nin övladlarıdır.

h e i g h t = min (h e i g h t, df s (t o, v, c n t + 1));

Əgər $h e i g h t = I NF$ -dirsə, onda $v$ təpəsi yarpaqdır və $h [v] = 0$ təyin edilir. Əks halda, qaytarılan qiymət:

h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])

  return h[v] = (height == INF) ? 0 : 1 + height;
}

dfs2 $(v, p)$ funksiyası təpə $v$ -dən başlayaraq DFS yerinə yetirir və $res [v]$ qiymətini qaytarır. Burada $p$ təpə $v$ -nin valideynidir.

int dfs2(int v, int p = -1)
{
  int s = 0;

$t_{1}, t_{2}, ..., t_{k}$ — $v$ təpəsinin övladlarıdır. $s$ dəyişənində aşağıdakı cəmi hesablayın:

res [t o_{1}] + res [t o_{2}] + ... + res [t o_{k}]

  for (int to : g[v])
    if (to != p)
    {
      dfs2(to, v);
      s += res[to];
    }

Əgər $h [v] \leq d [v]$ -dirsə, bir dost kifayətdir və $res [v] = 1$ olacaq. Əks halda

res [v] = res [t o_{1}] + res [t o_{2}] + ... + res [t o_{k}] = s

  return res[v] = (h[v] <= d[v]) ? 1 : s;
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyun. Qrafı qurun.

scanf("%d", &n);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  g[b].push_back(a);
}

Massivləri (arayları) başladın.

d.resize(n + 1);
h.resize(n + 1);
res.resize(n + 1);

İki dəfə dərinlik üzrə keçid (DFS) həyata keçirin. Birinci keçid hər bir $v$ təpəsi üçün $d [v]$ və $h [v]$ qiymətlərini hesablayır.

dfs(1);
dfs2(1);

Cavabı çap edin — kəpənəyi tutmaq üçün lazım olan minimum dostların sayı.

printf("%lld\n", res[1]);

Kefa ilk böyük maaşını qeyd etmək üçün restorana getmək qərarına gəldi.

O, qeyri-adi bir parkın yaxınlığında yaşayır. Park $n$ təpədən ibarət köklü bir ağacdır və kök $1$ -ci təpədir. Kefa-nın evi də $1$ -ci təpədə yerləşir. Təəssüf ki, park pişiklərlə doludur və Kefa artıq hansı təpələrdə pişiklərin olduğunu müəyyən edib.

Parkın yarpaq təpələrində restoranlar yerləşir. Kefa restoran seçmək istəyir, lakin o, pişiklərdən çox qorxur. Buna görə də, əgər evindən restorana qədər yolda $m$ -dən çox ardıcıl pişik olan təpə varsa, o, həmin restorana getməyəcək.

Sizin vəzifəniz — Kefa-nın təhlükəsiz şəkildə gedə biləcəyi restoranların sayını hesablamaqdır.

Giriş. Birinci sətrdə iki tam ədəd verilir: $n$ və $m (2 \leq n \leq 1 0^{5}, 1 \leq m \leq n)$ — ağacdakı təpələrin sayı və Kefa-nın dözə biləcəyi maksimum ardıcıl pişik olan təpə sayı.

İkinci sətrdə $n$ tam ədəd verilir: $a_{1}, a_{2}, ..., a_{n}$ , burada hər bir $a_{i}$ ya $0$ (təpədə pişik yoxdur), ya da $1$ (təpədə pişik var) olur.

Sonrakı $n - 1$ sətirdə ağacın qıraqları $x_{i} y_{i} (1 \leq x_{i}, y_{i} \leq n, x_{i} \neq = y_{i})$ formatında verilir, burada $x_{i}$ və $y_{i}$ bir qıraqla birləşdirilmiş təpələrdir.

Verilən qıraq dəstinin ağac yaratdığına zəmanət verilir.

Çıxış. Kefa-nın evindən başlayaraq yolu boyunca $m$ -dən artıq ardıcıl pişik olmayan yarpaq təpələrə çatmaq imkanlarının sayını çap edin.

Məsələyə keçid

Pişiklərin yerləşdiyi məlumatlar $c a t s$ massivində saxlanılır. Ağac isə bitişik siyahı şəklində $g$ massivində saxlanılır.

vector<int> cats;
vector<vector<int> > g;

dfs funksiyası $v$ təpəsindən dərinlik üzrə axtarış aparır və bu təpədən hansı restoranlara çatmaq mümkün olduğunu qaytarır (şərtlə ki, yol boyunca ardıcıl pişik olan təpələrin sayı $m$ -dən çox olmasın). $p re v$ — $v$ təpəsinin valideynidir. $c n t$ isə $v$ daxil olmaqla indiyə qədər ardıcıl pişik olan təpələrin sayıdır.

int dfs(int v, int prev, int cnt)
{

Əgər artıq $m$ -dən çox ardıcıl pişik olan təpələr keçilibsə, axtarış davam etmir.

  if (cnt > m) return 0;

Əgər yarpaq təpədəyiksə, çatmaq mümkün olan restoranların sayını artır.

  if (g[v].size() == 1 && prev != -1) return 1;

$res$ dəyişənində $v$ təpəsindən çatmaq mümkün olan restoranların sayı toplanır.

  int res = 0;

$v$ təpəsindən çıxan bütün $(v, t o)$ qıraqlarını gəz. Əgər $t o$ $v$ -nin valideynidirsə, bu təpəyə keçmə.

  for (int to : g[v])
    if (to != prev) 
    {

Əgər $t o$ təpəsində pişik yoxdursa, $c = 0$ təyin et. Əks halda $c = c n t + 1$ . $c$ dəyişəni $t o$ təpəsinə qədər (daxil olmaqla) olan ardıcıl pişikli təpələrin sayını saxlayır.

      int c = (cats[to] == 0) ? 0 : cnt + 1;

$t o$ təpəsindən DFS-i davam etdir.

      res += dfs(to, v, c);
    }

Nəticəni qaytar.

  return res;
}

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

scanf("%d %d", &n, &m);
cats.resize(n + 1);
for (i = 1; i <= n; i++)
  scanf("%d", &cats[i]);

Ağacı qur.

g.resize(n + 1);
for (i = 1; i < n; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  g[b].push_back(a);
}

Nəticəni çap et. dfs funksiyası $1$ təpəsindən çağırılır və məsələnin cavabını qaytarır. Çünki $1$ təpəsinin valideyni yoxdur, ikinci parametr kimi $- 1$ ötürülür. $1$ təpəsindən başladıqda, artıq $c a t s [1]$ qədər pişiklə qarşılaşmışıq.

printf("%d\n", dfs(1, -1, cats[1]));

Python reallaşdırılması

def dfs(v, prev, cnt):

Əgər artıq $m$ -dən çox ardıcıl pişik olan təpə keçilibsə, axtarış davam etmir.

  if cnt > m:
    return 0

Əgər yarpaq təpədəyiksə, çatmaq mümkün olan restoranların sayını artır.

  if len(g[v]) == 1 and prev != -1:
    return 1

$res$ dəyişənində $v$ təpəsindən çatmaq mümkün olan restoranların sayı toplanır.

  res = 0

$v$ təpəsindən çıxan bütün $(v, t o)$ qıraqlarını gəz. Əgər $t o$ $v$ -nin valideynidirsə, bu təpəyə keçmə.

  for to in g[v]:
    if to != prev:

      c = 0 if cats[to] == 0 else cnt + 1

$t o$ təpəsindən DFS-i davam etdir.

      res += dfs(to, v, c)

Nəticəni qaytar.

  return res

Əsas hissə. Giriş məlumatlarını oxu.

n, m = map(int, input().split())
cats = [0] + list(map(int, input().split()))

Ağacı qur.

g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)

print(dfs(1, -1, cats[1]))

$d (i, j) = d (i, 1) - d (j, 1)$ şərti yalnız və yalnız $j$ təpəsi $i$ təpəsinin DFS-də (dərinlik üzrə axtarış) əcdadı olduqda doğrudur.

Gəlin bir nümunəyə baxaq:

$d (4, 1) = 2$ , $d (4, 1) - d (1, 1) = 2 - 0 = 2$ ;
$d (6, 3) = 2$ , $d (6, 1) - d (3, 1) = 3 - 1 = 2$ ;
$d (2, 2) = 0$ , $d (2, 1) - d (2, 1) = 1 - 1 = 0$ ;
$d (6, 1) = 3$ , $d (6, 1) - d (1, 1) = 3 - 0 = 3$ ;

Gəlin $h [v]$ ilə təpə $v$ -nin dərinliyini təyin edək — bu, kökdən ( $1$ təpəsindən) $v$ -yə qədər olan yol üzərindəki təpələrin sayıdır. Şəkildə hər bir təpənin yanında onun dərinliyi göstərilmişdir.

İndi $i$ təpəsini sabit saxlayaraq soruşaq: neçə $j$ təpəsi var ki, $d (i, j) = d (i, 1) - d (j, 1)$ bərabərliyi ödənir?

Məsələn, $i = 6$ üçün belə $4$ təpə var: $j = 1, 3, 4, 6$ . Burada $h [6] = 4$ . Deməli, sabit bir $i$ üçün $h [i]$ sayda uyğun $j$ mövcuddur.

Buna görə də məsələni həll etmək üçün hər bir təpə üçün $h [v]$ dərinliyini hesablamaq və sonra bütün bu dərinliklərin cəmini tapmaq lazımdır.

Nümunə

Gəlin nümunədəki qrafı nəzərdən keçirək. Hər bir təpənin yanında onun dərinliyi göstərilmişdir.

Bütün təpələrin dərinliklərinin cəmi: $1 + 2 + 3 + 3 + 4 = 13$ .

Qrafın qonşuluq siyahısını $g$ kimi müəyyən edək. Təpələrin dərinlikləri $h$ massivində saxlanılır.

vector<vector<int> > g;
vector<int> h;

dfs funksiyası hər bir təpənin dərinliyini hesablayır. $v$ təpəsinin valideyni $p$ təpəsidir.

int dfs(int v, int p)
{
  for (int to : g[v])

$(v, t o)$ qırağını nəzərdən keçir. Əgər $t o$ təpəsi $v$ -nin valideyni deyilsə, onun dərinliyini hesabla və ondan DFS başlat.

    if (to != p)
    {
      h[to] = h[v] + 1;
      dfs(to, v);
    }
  return h[v];
}

Proqramın əsas hissəsi. Ağacdakı təpələrin sayını oxu.

scanf("%d", &n);
g.resize(n + 1);

Ağacı qur.

for (i = 2; i <= n; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  g[b].push_back(a);
}

$1$ təpəsinin dərinliyini $1$ olaraq təyin et.

h.resize(n + 1);
h[1] = 1;

DFS-i $1$ təpəsindən başlat.

dfs(1, -1);

Cavabı hesabla — bütün təpələrin dərinliklərinin cəmi.

res = 0;
for (i = 1; i <= n; i++)
  res += h[i];

Cavabı çap et.

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

İkiyollu bir ağac verilib, yəni $n$ təpə və $n - 1$ qıraqlı, dövrə olmayan və əlaqəli qraf. Hər bir təpənin dərəcəsi maksimum $3$ -dür. Kök təpə $1$ -dir və onun dərəcəsi $2$ -dən artıq deyil.

Təəssüf ki, kök təpəsi yoluxub. Aşağıdakı proses $n$ dəfə təkrarlanır:

Hüseyn hər dövrədə ya hələ yoluxmamış (və silinməmiş) bir təpəni seçib onu və ona birləşən bütün qıraqları silir, ya da heç bir şey etmir.
Bundan sonra yoluxma prosesi baş verir: artıq yoluxmuş təpələrə birbaşa bağlı olan bütün təpələr yoluxur (əvvəlki yoluxmuşlar yoluxmuş qalır).

Hüseynə maksimum neçə təpəni yoluxmadan xilas edə biləcəyini tapmağa kömək et (qeyd edək ki, silinmiş təpələr xilas olunmuş sayılmır).

Giriş. İlk sətirdə təpələrin sayı $n (2 \leq n \leq 3 \cdot 1 0^{5})$ verilir.

Növbəti $n - 1$ sətirdə $u_{i}$ və $v_{i} (1 \leq u_{i}, v_{i} \leq n)$ cütlükləri verilir — bu, ağacdakı bir qırağı təsvir edir.

Zəmanət verilir ki, verilmiş qraf kökü $1$ olan iki yollu ağacdır.

Çıxış. Xilas edilə biləcək maksimum təpələrin sayını verin.

Problemi aç

Hər bir $v$ təpəsi üçün onun kök olduğu altqrafdakı təpələrin sayını $s u m [v]$ kimi hesablayırıq. Əgər $t o_{1}, t o_{2}, ..., t o_{k}$ — $v$ təpəsinin övladlarıdırsa, o zaman

s u m [v] = 1 + s u m [t o_{1}] + s u m [t o_{2}] + ... + s u m [t o_{k}]

Əgər $v$ təpəsi yarpaqdırsa, onda $s u m [v] = 1$ .

$d p [v]$ — kökü $v$ olan altqrafda yoluxmadan xilas edilə biləcək təpələrin sayıdır (əgər yalnız $v$ təpəsi yoluxubsa).

Əgər $v$ təpəsinin yalnız bir övladı $t o$ varsa, onda $d p [v] = s u m [t o] - 1$ (çünki $t o$ silinir və xilas olunmuş sayılmır).

Əgər $v$ təpəsinin iki övladı var — $t o_{1}$ və $t o_{2}$ , o zaman iki variant var:

$t o_{1}$ təpəsini silmək və $t o_{2}$ altqrafındakı təpələri xilas etmək: $s u m [t o_{1}] - 1 + d p [t o_{2}]$ .
$t o_{2}$ təpəsini silmək və $t o_{1}$ altqrafındakı təpələri xilas etmək: $s u m [t o_{2}] - 1 + d p [t o_{1}]$ .

Bu iki variantdan maksimumunu seçirik.

DFS zamanı $(v, t o)$ qırağını keçərkən aşağıdakı şəkildəki vəziyyəti nəzərdən keçirək:

$t o v$ təpəsinin ikinci övladı $a$ -dır. Biz $d p [t o] + s u m [a] - 1$ ifadəsini hesablamaq istəyirik. Bunun üçün yalnız $v$ və $t o$ təpələrindən istifadə edirik. Aşağıdakı bərabərlik doğrudur:

s u m [v] = 1 + s u m [t o] + s u m [a]

Bundan belə nəticə çıxır ki:

sum [a] = sum [v] - sum [t o] - 1

Bu halda,

dp [t o] + sum [a] - 1 = dp [t o] + sum [v] - sum [t o] - 2

Beləliklə, təpə $v$ üçün övladları $t o$ üzərində iterasiya edib aşağıdakı maksimumu tapırıq:

dp [v] = max (dp [t o] + sum [v] - sum [t o] - 2)

Nümunə

Birinci nümunədə Huseyn $2$ -ci təpəni ilk gediş olaraq silməklə $3$ və $4$ təpələrini xilas edə bilər.

İkinci nümunəyə baxaq. Hər təpənin yanında $s u m [v] / d p [v]$ dəyərləri qeyd olunmuşdur. Huseynin seçdiyi təpələr yaşıl rənglə göstərilmişdir.

Məsələn,

dp [1] = max (sum [2] - 1 + dp [5], sum [5] - 1 + dp [2]) = max (2, 2) = 2, sum [1] = 1 + sum [2] + sum [5] = 1 + 3 + 3 = 7

Massivləri elan edək:

#define MAX 300005
int sum[MAX], dp[MAX];
vector<vector<int>> g;

dfs funksiyası təpə $v$ -dən başlayaraq DFS icra edir. $p$ — $v$ təpəsinin valideynidir.

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

$s u m [v]$ və $d p [v]$ -ni ilkinləşdiririk:

  sum[v] = 1;
  dp[v] = 0;

Təpə $v$ -nin övladları üzrə DFS icra edirik:

  for (int to : g[v])
    if (to != p)
    {
      dfs(to, v);
      sum[v] += sum[to];
    }

$d p [v]$ dəyərini hesablayaq:

  for (int to : g[v])
    if (to != p)
    {
      dp[v] = max(dp[v], sum[to] - 1); // əgər yalnız bir övladı varsa
      dp[v] = max(dp[v], dp[to] + sum[v] - sum[to] - 2); // əks halda, maksimumu götür
    }
}

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

scanf("%d", &n);
g.clear(); g.resize(n + 1);
memset(dp, 0, sizeof(dp));
memset(sum, 0, sizeof(sum));
for (i = 1; i < n; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  g[v].push_back(u);
}

Dərinlikə-öncə axtarışı $1$ -ci təpədən başlat.

dfs(1);

Cavabı çap et.

printf("%d\n", dp[1]);

Məsələlərin siyahısı

Şərhlər (5)

user767927•2 ay öncə•2-ci təftiş

сайт розповідає з чого складається, як зробити

user897042•4 ay öncə

what a community i asked for help and noone cares.

user897042•4 ay öncə

https://codeforces.com/contest/315/problem/B how to solve this problem i wrote two updates one for assinging and second for interval with lazy. but it doesnt seem to work because two seperate updates doesnt have link between them.

medv•4 ay öncə

user897042 https://site.ada.edu.az/~medv/acm/Docs%20e-olimp/Volume%209/853_English.htm

user897042•4 ay öncə

user897042 need help on these two too:https://codeforces.com/contest/1857/problem/Ghttps://codeforces.com/contest/1702/problem/G

Yüklənir

Bir an, serverdən məlumat alınır