Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- vector< vector<bool> > grafo,grafo2;
- vector<int> valor;
- stack<int> caminho;
- int n,nivel=0,busca,total=0;
- int getFilho(int pai){
- for(int cont=0;cont<n;cont++){
- if(grafo2[pai][cont] == true || grafo2[cont][pai] == true)
- return cont;
- }
- return -1;
- }
- void dfs(int atual){
- int filho = getFilho(atual);
- if(valor[atual] == busca){
- total+=nivel;
- valor[atual] = -1;
- }else if(filho != -1){
- grafo2[atual][filho] = false;
- grafo2[filho][atual] = false;
- caminho.push(atual);
- nivel++;
- dfs(filho);
- }else if(!caminho.empty()){
- int pai = caminho.top();
- caminho.pop();
- nivel--;
- dfs(pai);
- }
- }
- int main(){
- scanf("%d",&n);
- for(int cont=0;cont<n;cont++){
- grafo.push_back(vector<bool>(n,false));
- }
- for(int cont=0;cont<n;cont++){
- int val;
- scanf("%d",&val);
- valor.push_back(val);
- }
- for(int cont=0;cont<n-1;cont++){
- int x,y;
- scanf("%d%d",&x,&y);
- x--;
- y--;
- grafo[x][y] = true;
- grafo[y][x] = true;
- }
- for(int cont=0;cont<n;cont++){
- if(valor[cont] != -1){
- grafo2 = grafo;
- nivel = 0;
- busca = valor[cont];
- valor[cont] =-1;
- dfs(cont);
- }
- }
- printf("%d\n",total );
- return 0;
- }
Add Comment
Please, Sign In to add comment