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

[Anonymous]

Sie erhalten einen ungewichteten 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 einfachen Pfad zwischen zwei gegebenen Knoten. Offline -Abfrage -Antwort ist zulässig.

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 
 Wenn t 2, ist es Typ 2 Abfrage, um die Summe von Werten auf dem einfachen Pfad zwischen a und b < /li> < /ul < /ul < /ul < /ul < /
Ein Beispieleingang ist < /p>
[code]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?