Beantworten Sie die Summe von Werten auf dem Baumpfad mit Aktualisierungen effizient ⇐ C++

[Anonymous]

Sie erhalten einen Baum mit N -Knoten und jeder Knoten beginnt mit Wert 0. Es gibt Q -Abfragen. Der 1. Abfrageart ändert den Wert an einem Knoten auf einen neuen Wert. Die zweite Abfragetyp fragt nach der Summe der Werte von Knoten auf dem kürzesten Pfad zwischen zwei gegebenen Knoten.

Code: Select all

#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>
und Ausgabe < /p>
10
15
10

Was ist eine effizientere Möglichkeit, diese Abfragen zu lösen?