Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2470
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2470
Jogo da Memória
Por OBI - Olimpíada Brasileira de Informática 2014 
Brazil
Timelimit: 1
Pedro e Paulo resolveram complicar um pouco o tradicional Jogo da Memória, em que os jogadores precisam virar duas cartas iguais. Eles colocam as cartas no chão, viradas para baixo, e fazem algumas linhas ligando pares de cartas, usando giz, de modo que para qualquer par de cartas (A, B) existe uma e apenas uma sequência de cartas distintas que leva de A até B através das linhas que eles desenharam. Com isso, ao virar duas cartas, o jogador ganha uma quantidade de pontos igual ao tamanho da sequência de linhas entre as duas cartas, se elas forem iguais. Se forem diferentes, o jogador perde aquela quantidade de pontos.
Pedro e Paulo, agora, estão estudando qual é a melhor estratégia para esse jogo e precisam da sua ajuda para resolver uma tarefa específica: dadas as ligações entre as N cartas, calcular a soma dos tamanhos das sequências entre todos os N/2 pares de cartas iguais!
O jogo possui N cartas, de índices 1 até N. Cada carta possui a figura de um número de 1 até N/2 desenhada. Exatamente duas cartas possuem a figura de cada número entre 1 e N/2.
Entrada
A primeira linha da entrada contém o número de cartas N (2 ≤ N ≤ 50000, N é par). A segunda linha da entrada contém N inteiros Ci (1 ≤ Ci ≤ N/2) , 1 ≤ i ≤ N, indicando qual número está anotado na carta de índice i. Cada uma das N −1 linhas seguintes contém dois números A e B (1 ≤ A, B ≤ N), indicando que existe uma linha desenhada entre as cartas de índices A e B.
Saída
Seu programa deve imprimir uma linha contendo um inteiro, a soma dos tamanhos das sequências entre todos os N/2 pares de cartas iguais.
| Exemplos de Entrada | Exemplos de Saída |
|
6 |
3 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define MAXN 50500
#define MAXL 21
int pai[MAXN], nivel[MAXN], carta[MAXN], par[MAXN], n, resposta, acessado[MAXN];
int ancestral[MAXN][MAXL];
vector<int> lista[MAXN];
void dfs(int u) {
for (int i = 0; i < lista[u].size(); i++) {
int v = lista[u][i];
if (nivel[v] == -1) {
nivel[v] = nivel[u] + 1;
pai[v] = u;
dfs(v);
}
}
}
int LCA(int u, int v) {
if (nivel[u] < nivel[v]) swap(u, v);
for (int i = MAXL - 1; i >= 0; i--) {
if (ancestral[u][i] != -1 && nivel[ancestral[u][i]] >= nivel[v]) {
u = ancestral[u][i];
}
}
if (u == v) return u;
for (int i = MAXL - 1; i >= 0; i--) {
if (ancestral[u][i] != ancestral[v][i] && ancestral[u][i] != -1) {
u = ancestral[u][i];
v = ancestral[v][i];
}
}
return pai[u];
}
int main() {
scanf("%d", &n);
for (int i = 1; i < = n; i++) {
int x;
scanf("%d", &x);
if (carta[x]) {
par[i] = carta[x];
par[carta[x]] = i;
}
carta[x] = i;
}
for (int i = 1; i < n; i++) {
int a, b;
scanf("%d %d", &a, &b);
lista[a].push_back(b);
lista[b].push_back(a);
}
memset(pai, -1, sizeof(pai));
memset(nivel, -1, sizeof(nivel));
nivel[1] = 0;
dfs(1);
for (int i = 1; i < = n; i++) ancestral[i][0] = pai[i];
for (int j = 1; j < MAXL; j++) {
for (int i = 1; i < = n; i++) {
if (ancestral[i][j - 1] != -1) {
ancestral[i][j] = ancestral[ancestral[i][j - 1]][j - 1];
}
}
}
for (int i = 1; i < = n; i++) {
if (acessado[i]) continue;
resposta += nivel[i] + nivel[par[i]] - 2 * nivel[LCA(i, par[i])];
acessado[i] = 1;
acessado[par[i]] = 1;
}
printf("%d\n", resposta);
}
Input
2 2 1 1 3 3
1 2
3 4
6 5
2 6
3 6
Output