米哈游 树中abb类型个数,求大佬解释一下为什么只过了95%
#include <bits/stdc++.h> using namespace std; struct Node { char val; set<Node *> next; int notEqual; Node(int v) : val(v), notEqual(0) {} }; int main() { int n = 0; int cur = 0, next = 0; string val; cin >> n; cin >> val; vector<Node *> tree(n + 1); set<vector<int>> candicates; for (int i = 1; i <= n; ++i) { tree[i] = new Node(val[i - 1]); } for (int i = 1; i < n; ++i) { cin >> cur >> next; if (tree[cur]->next.find(tree[next]) != tree[cur]->next.end()) continue; tree[cur]->next.insert(tree[next]); tree[next]->next.insert(tree[cur]); if (tree[cur]->val == tree[next]->val) { candicates.insert({cur, next}); } else { ++tree[cur]->notEqual; ++tree[next]->notEqual; } } int ans = 0; for (auto &candicate : candicates) { ans += tree[candicate[0]]->notEqual += tree[candicate[1]]->notEqual; } cout << ans << endl; return 0; }
#米哈游笔试#