Ответ сумма значений на пути дерева, с обновлениями, эффективно ⇐ C++

[Anonymous]

Вам дают дерево с N -узлами, и каждый узел начинается со значения 0. Будут Q запросов. 1 -й тип запроса изменит значение в узле на новое значение. 2 -й тип запроса запрашивает сумму значений узлов на кратчайшем пути между двумя данными узлами.

Код: Выделить всё

#include 
#include 
#include 
using namespace std;
const int MAX_INPUT = 1e5 + 5;
vector graph[MAX_INPUT];
int values[MAX_INPUT];
bool seen[MAX_INPUT];
long long getSum(int from, int to) {
if (seen[from]) {
return -1;
}
seen[from] = true;
if (from == to) {
return values[from];
}
for (int n : graph[from]) {
int nsum = getSum(n, to);
if (nsum >= 0) {
return values[from] + nsum;
}
}
return -1;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N;
cin >> N;
for (int i = 0; i < N - 1; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
int Q;
cin >> Q;
for (int q = 0; q < Q; q++) {
int type;
cin >> type;
if (type == 1) {
int node, newvalue;
cin >> node >> newvalue;
values[node] = newvalue;
} else {
int node1, node2;
cin >> node1 >> node2;
memset(seen, 0, N + 1);
long long pathsum = getSum(node1, node2);
cout 
5
1 2
1 5
2 3
2 4
5
1 2 10
2 3 4
1 1 5
2 2 5
2 4 3
< /code>
и вывод < /p>
10
15
10

Какой более эффективный способ решить эти запросы?

Подробнее здесь: https://stackoverflow.com/questions/797 ... fficiently