米哈游 树中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;
} #米哈游笔试#
腾讯成长空间 5958人发布