Унікальний колір#10654

Унікальний колір (Розбір)

Запустим пошук в глибину з вершини $1$ . При вході в вершину $v$ кольору $co l or [v]$ color[v] збільшимо значення $u se d [co l or [v]]$ used[color[v]] на $1$ . Значення $u se d [co l or [v]]$ used[color[v]] містить, скільки разів колір $co l or [v]$ color[v] зустрівся на шляху від вершини $1$ до вершини $v$ (включно). Якщо колір $co l or [v]$ color[v] на цьому шляху зустрівся лише один раз, значить вершина $v$ є хорошою, і ми додаємо її в результатуючу множину.

При виході з вершини $v$ значення $u se d [co l or [v]]$ used[color[v]] слід зменшити на $1$ .

Приклад

Граф з першого прикладу виглядає наступним чином:

Вершина $5$ не є хорошою, так як на шляху $1 - 2 - 5$ 1 - 2 - 5 вершини $5$ та $1$ мають однаковий колір.

Вершина $6$ є хорошою, так як на шляху $1 - 2 - 3 - 6$ 1 - 2 - 3 - 6 кольори всіх проміжних вершин відрізняються від кольору вершини $6$ .

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

Вхідний граф зберігаємо в списку суміжності $g$ . Оголосимо робочі масиви.

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

Функція dfs реалізує пошук в глибину. Змінна $p a r$ є предком вершини $v$ .

void dfs(int v, int par)
{

Вершина $v$ має колір $co l or [v]$ color[v]. Позначаємо, що на шляху від вершини $1$ зустрілася вершина цього кольору.

  used[color[v]]++;

Значення $u se d [co l or [v]]$ used[color[v]] показує, скільки разів колір $co l or [v]$ color[v] зустрівся на шляху від вершини $1$ до вершини $v$ (включно). Якщо цей колір зустрівся на шляху рівно один раз, то вершина $v$ вважається хорошою, і ми додаємо її в результатуючу множину $s t$ .

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

Перебираємо всі ребра $(v, t o)$ (v, to), виходячі з вершини $v$ . Якщо вершина $t o$ не є предком $v (t o \neq = p a r)$ v~(to \ne par), запускаємо з неї пошук в глибину. При цьому предком $t o$ стає $v$ .

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

При виході з вершини $v$ зменшуємо значення $u se d [co l or [v]]$ used[color[v]] на $1$ .

  used[color[v]]--;
}

Основна частина програми. Читаємо кількість вершин $n$ та масив кольорів.

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

Читаємо граф.

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

C++

Запускаємо пошук в глибину з вершини $1$ .

dfs(1, 1);

Виводимо хороші вершини. Вони містяться в множині $s t$ .

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