XOR cəmi#10653

XOR cəmi (Həll təhlili)

Dərinlik üzrə axtarışın köməyi ilə 1-ci zirvə ilə qalan zirvələr arasında XOR cəmi hesablayacağıq. Zirvələr 1 və $v$ arasında XOR cəmini $x [v]$ -yə yerləşdirəcəyik. Gəlin $o n es$ -ləri $x$ massivindəki birlərin, və $z er oes$ -ləri sıfırların sayı olaraq təyin edək $(o n es + z er oes = n)$ (ones + zeroes = n). Onda məsələnin cavabı $o n es \cdot z er oes$ ones \cdot zeroes sayına bərabərdir.

Nümunə

Qraf və onun misalını nəzərdən keçirək.

Hər bir zirvənin $v$ yanında 1 və $v$ arasındaki XOR cəmi $x [v]$ yazılır. Əgər $x [v] = x [u]$ x[v] = x[u] bərabərdirsə zirvələr $v$ və $u$ , onda onların aralarındaki XOR cəmi $0$ olur, beləliklə, toplam $0$ verir. $x [v] \neq = x [u]$ x[v] \ne x[u] olan hər bir zirvə cütlüyü $(v, u)$ üçün XOR cəmi toplamda $1$ verir.

Nəticədə cavab $x [v] \neq = x [u]$ x[v] \ne x[u] olan zirvə cütlüklərinin $(v, u)$ sayına bərabərdir. Bu say $o n es \cdot z er oes = 2 \cdot 3 = 6$ ones \cdot zeroes = 2 \cdot 3 = 6 olur. Toplamı 1 edən zirvə cütləri olacaq: $(1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (4, 5)$ (1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (4, 5).

Alqoritmin reallaşdırılması

Giriş qrafını qonşuluq siyahısında $g$ saxlayaq. $x$ massivini elan edək.

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

dfs funksiyası 1 və $v$ zirvələri arasında $x [v]$ XOR cəmini hesablayan dərinlik üzrə axtarışı reallaşdırır. 1 və $v$ arasında cari XOR cəmi $c u r_x or$ cur\_xor bərabərdir. Zirvə $v$ -nin ata nöqtəsi $p$ -dir.

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

C++

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

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

C++

Dərinlik üzrə axtarışı 1 zirvəsindən başladırıq.

dfs(1, 0, -1);

$x$ massivindəki sıfırlar $z er oes$ və birləri $o n es$ sayını hesablayırıq.

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

Cavabı çıxışa veririk.

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

Python reallaşdırılması

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ş qrafını oxuyuruq.

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 iniləşdiririk.

x = [0] * (n + 1)

Dərinlik üzrə axtarışı 1 zirvəsindən başladırıq.

dfs(1)

$x$ massivindəki sıfırlar $z er oes$ və birləri $o n es$ sayını hesablayırıq.

ones = sum(x)
zeroes = n - ones

Cavabı çıxışa veririk.

print(ones * zeroes)