#include <iostream> #include <stdio.h> #include <cstdio> using namespace std; bool hasColor(int color, int nNodes, int colors[]) { for (int i = 0; i < nNodes; i++) { if (colors[i] == color) { return true; } } return false; } int findLineStart(int nNodes, int connections[][2]) { int powerOfNode[nNodes]; for (int i = 0; i < nNodes; i++) { powerOfNode[i] = 0; } for (int i = 0; i < nNodes - 1; i++) { powerOfNode[connections[i][0]]++; powerOfNode[connections[i][1]]++; } int lineStart = -2; for (int i = 0; i < nNodes; i++) { if (powerOfNode[i] > 2) { return -1; } else if (powerOfNode[i] == 1) { lineStart = i; } } return lineStart; } int countColorSwitches(int nNodes, int colors[], int connections[][2]) { int colorSwitches = 0; for (int i = 0; i < nNodes - 1; i++) { if (colors[connections[i][0]] != colors[connections[i][1]]) { colorSwitches++; } } return colorSwitches; } bool solve() { int nNodes; cin >> nNodes; int originalColors[nNodes]; int targetColors[nNodes]; int connections[nNodes - 1][2]; for (int i = 0; i < nNodes; i++) { int color = getchar() - '0'; if (color == 0 || color == 1) { originalColors[i] = color; } else { i--; } } for (int i = 0; i < nNodes; i++) { int color = getchar() - '0'; if (color == 0 || color == 1) { targetColors[i] = color; } else { i--; } } for (int i = 0; i < nNodes - 1; i++) { cin >> connections[i][0]; connections[i][0]--; cin >> connections[i][1]; connections[i][1]--; } if (hasColor(0, nNodes, targetColors) && !hasColor(0, nNodes, originalColors) || hasColor(1, nNodes, targetColors) && !hasColor(1, nNodes, originalColors)) { return false; } int originalSwitches = countColorSwitches(nNodes, originalColors, connections); int targetSwitches = countColorSwitches(nNodes, targetColors, connections); int lineStart = findLineStart(nNodes, connections); if (lineStart >= 0) { if (originalColors[lineStart] == targetColors[lineStart]) { return targetSwitches <= originalSwitches; } else { return targetSwitches < originalSwitches; } } else { if (targetSwitches < nNodes - 1) { return true; } // must be identical for (int i = 0; i < nNodes; i++) { if (originalColors[i] != targetColors[i]) { return false; } } return true; } } int main() { int nTests; cin >> nTests; for (int i = 0; i < nTests; i++) { if (solve()) { printf("TAK\n"); } else { printf("NIE\n"); } } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 | #include <iostream> #include <stdio.h> #include <cstdio> using namespace std; bool hasColor(int color, int nNodes, int colors[]) { for (int i = 0; i < nNodes; i++) { if (colors[i] == color) { return true; } } return false; } int findLineStart(int nNodes, int connections[][2]) { int powerOfNode[nNodes]; for (int i = 0; i < nNodes; i++) { powerOfNode[i] = 0; } for (int i = 0; i < nNodes - 1; i++) { powerOfNode[connections[i][0]]++; powerOfNode[connections[i][1]]++; } int lineStart = -2; for (int i = 0; i < nNodes; i++) { if (powerOfNode[i] > 2) { return -1; } else if (powerOfNode[i] == 1) { lineStart = i; } } return lineStart; } int countColorSwitches(int nNodes, int colors[], int connections[][2]) { int colorSwitches = 0; for (int i = 0; i < nNodes - 1; i++) { if (colors[connections[i][0]] != colors[connections[i][1]]) { colorSwitches++; } } return colorSwitches; } bool solve() { int nNodes; cin >> nNodes; int originalColors[nNodes]; int targetColors[nNodes]; int connections[nNodes - 1][2]; for (int i = 0; i < nNodes; i++) { int color = getchar() - '0'; if (color == 0 || color == 1) { originalColors[i] = color; } else { i--; } } for (int i = 0; i < nNodes; i++) { int color = getchar() - '0'; if (color == 0 || color == 1) { targetColors[i] = color; } else { i--; } } for (int i = 0; i < nNodes - 1; i++) { cin >> connections[i][0]; connections[i][0]--; cin >> connections[i][1]; connections[i][1]--; } if (hasColor(0, nNodes, targetColors) && !hasColor(0, nNodes, originalColors) || hasColor(1, nNodes, targetColors) && !hasColor(1, nNodes, originalColors)) { return false; } int originalSwitches = countColorSwitches(nNodes, originalColors, connections); int targetSwitches = countColorSwitches(nNodes, targetColors, connections); int lineStart = findLineStart(nNodes, connections); if (lineStart >= 0) { if (originalColors[lineStart] == targetColors[lineStart]) { return targetSwitches <= originalSwitches; } else { return targetSwitches < originalSwitches; } } else { if (targetSwitches < nNodes - 1) { return true; } // must be identical for (int i = 0; i < nNodes; i++) { if (originalColors[i] != targetColors[i]) { return false; } } return true; } } int main() { int nTests; cin >> nTests; for (int i = 0; i < nTests; i++) { if (solve()) { printf("TAK\n"); } else { printf("NIE\n"); } } return 0; } |