-
Notifications
You must be signed in to change notification settings - Fork 3
/
main.cpp
68 lines (50 loc) · 1.49 KB
/
main.cpp
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
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int val;
char sym;
vector<Node *> children;
Node(int val, char sym) : val(val), sym(sym) {}
};
void findBranches(Node *curr, int val, const string &word, vector<pair<int, string>> &branches) {
if (curr->children.empty()) {
branches.emplace_back(val, word);
return;
}
for (auto child: curr->children) {
findBranches(child, val + child->val, word + child->sym, branches);
}
}
int sumVal(Node *u, Node *v) {
int sum = 0;
vector<pair<int, string>> uBranches, vBranches;
findBranches(u, 0, "", uBranches);
findBranches(v, 0, "", vBranches);
for (int i = 0; i < uBranches.size(); i++) {
for (int j = 0; j < vBranches.size(); j++) {
if (uBranches[i].second == vBranches[i].second) {
sum += uBranches[i].first + vBranches[i].first;
}
}
}
return sum;
}
int main() {
Node *root = new Node(-1, ' ');
Node *n1 = new Node(1, 'a');
Node *n2 = new Node(2, 'a');
Node *nn1 = new Node(2, 'b');
Node *nn2 = new Node(1, 'b');
Node *nnn1 = new Node(3, 'c');
Node *nnn2 = new Node(3, 'c');
nn1->children.push_back(nnn1);
nn2->children.push_back(nnn2);
n1->children.push_back(nn1);
n2->children.push_back(nn2);
root->children.push_back(n1);
root->children.push_back(n2);
cout << sumVal(n1, n2) << endl;
cout << sumVal(nn1, nn2) << endl;
return 0;
}