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

[Anonymous]

Вам дают невзвешенное дерево с N -узлами, и каждый узел начинается со значения 0. Будут Q -запросы. 1 -й тип запроса изменит значение в узле на новое значение. 2 -й тип запроса запрашивает сумму значений узлов на простом пути между двумя данными узлами. Ответ о автономном запросе разрешен. < /P>
Я пытался хранить все значения узлов в массиве и запустить DFS, чтобы найти сумму пути, но он превышает 1S -ограничение. < /P>

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

#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 

 Первая строка - N (количество узлов) < /li>
 Следующие n - 1 строки содержат два номера узлов, которые дают преимущество в дереве (номера узлов являются целыми до 1 и n) < /li>
Q (номер Q (номер Q (номер Q (номер Q (номер Q (номер Q -номеры. />  Следующие Q Строки имеют по 3 целых числа T, A, B < /li>
 Если t равен 1, это запрос типа 1, чтобы установить значение в узле A до b < /li>
 Если t - 2, это запрос типа 2, чтобы спросить сумму значений узлов на простом пути между и б < /li>
. /> < /ul>
Пример ввода - < /p>
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