Para efeitos da nota atribuida à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 1 de Junho
(o problema continuará depois disponível para submissão, mas sem contar para a nota)
[para perceber o contexto do problema deve ler o guião da aula #10]

[DAA 040] Estradas romanas
(este problema é essencialmente uma tradução/adaptação de um problema do CodeChef)

Na antiga civilização romana existiam N cidades e M estradas bidirecionais que as ligavam. À medida que o tempo passou algumas estradas ficaram inutilizáveis, e ninguém as reparou.

Como um estudioso da civilização romana, queres agora fazer um pequeno estudo. Com esse propósito em mente, queres escrever um programa capaz de processar os seguintes tipos de operações:

• D K: indicando que a estrada com o número K no input ficou inutilizável. As estradas são numeradas consecutivamente a partir de 1 pela ordem em que aparecem no input.
• P A x: indicando que a população da A-ésima cidade passou a ser x. As cidades são também numeradas a partir de 1.

Chamemos a um subconjunto de cidades uma região se for possível viajar entre qualquer par de cidades do subconjunto usando as estradas ainda usáveis, possivelmente via algumas cidades intermédias do subconjunto. A população de uma região é a soma das populações das regiões que a constituem.

O Problema

Recebendo como input o sistema inicial de estradas, a população inicial de cada cidade e Q operações de um dos dois tipos anteriores, a tua tarefa é saber o tamanho da região mais populada depois de cada operação.

Input

A primeira linha contém três inteiros N M Q, indicando respetivamente o número N de cidades, o número M de estradas e o número Q de operações.

Segue-se uma linha com N inteiros, o i-ésimo dos quais indicando a população inicial da i-ésima cidade.

As M linhas seguintes indicam as estradas existentes no formato X Y indicando que existe uma estrada bidirecional entre as cidades X e Y. No início todas as estradas são usáveis.

As Q linhas seguintes indicam as operações a considerar no formato descrito anteriormente. É garantido que a mesma estrada nunca é indicada como inutilizável duas vezes

Output

O output deve ser constituído por Q linhas, uma por cada operação. Na i-ésima linha deve vir a população total da região mais populada depois de feitas as primeiras i operações.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Exemplo de Input

3 3 6
1 2 3
1 2
2 3
3 1
P 1 3
D 1
P 2 3
D 2
P 3 10
D 3

Exemplo de Output

8
8
9
6
13
10

Explicação do Input/Output

• Depois da 1ª operação as populações são (3, 2, 3) e a região mais populada é {1, 2, 3}.
• Depois da 2ª operação as populações e regiões mantêm-se as mesmas
• Depois da 3ª operação as populações são (3, 3, 3) e a região mais populada é {1, 2, 3}.
• Depois da 4ª operação as populações são as mesmas, mas temos agora duas regiões: {1, 3} e {2}. A região mais populada é {1, 3}.
• Depois da 5ª operação as populações são (3, 3, 10) e a região mais populada é novamente {1, 3}.
• Depois da 6ª e última operação as populações são as mesmas, mas agora cada cidade forma a sua própria região e a região mais populada é {13}.

Desenho e Análise de Algoritmos (CC2001)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto