14291

#include <iostream>
#include <vector>
#include <sstream>
#include <limits>
// Assume no invalid operation
void FindMaximumPath(std::vector<std::vector<long long int>> &directed_graph, std::vector< long long int> &parent,
                std::vector<long long int> &value,
                long long int &max_value, long long int &root_res, long long int current, long long int previous)
{
    // The idea is that for each node, we find 2 paths
    // (the paths from that node to any depth and yields the maximum path)
    // In other words, these 2 paths for each node are the maximum path and the second maximum path.
    // the maximum among all the nodes are the maximum path of the tree
    long long int first_max_path = 0;
    long long int second_max_path = 0;
    for (auto child : directed_graph[current]) {
        FindMaximumPath(directed_graph, parent, value, max_value, root_res, child, current);

        if (first_max_path <= value[child]) {
            second_max_path = first_max_path;
            first_max_path = value[child];
        } else {
            if (second_max_path <= value[child]) {
                second_max_path = value[child];
            }
        }
    }

    if (max_value <= first_max_path + second_max_path + value[current]) {
        max_value = first_max_path + second_max_path + value[current];
        root_res = current;
    }
    value[current] += first_max_path; // we need to store the maximum path so far into the nodes that we have visited
}

void print_test_graph(std::vector<std::vector<long long int>> &v) {
    int i = 0;
    for (auto x : v) {
        std::cout << i << ' ';
        for (auto y : x) {
            // print pair
            std::cout << y << " ";
        }
        ++i;
        std::cout << '\n';
    }
}
void print_test(std::vector<long long int> &v) {
    int i = 0;
    for (int i = 0; i < v.size(); ++i) {
        std::cout << i << ", " << v[i] << '\n';
    }
}
int main() {
    int n, op;
    // pair of {dest, distance}
    std::cin >> n >> op;
    // no clue why n + op + 1 does not work as size
    std::vector<std::vector<long long int>> directed_graph(20005);
    // this vector stores the value of each node_i and later on, the maximum path at node_i
    std::vector<long long int> value(20005);
    std::vector<long long int> parent(20005);
    std::fill(parent.begin(), parent.end(), -1);

    long long int src, dest, d;
    std::cin >> src >> d;
    long long int root = src;
    value[src] = d;
    parent[src] = -1; // we denotes no parents aka root also as -1
    for (int i = 0; i < n; ++i) {
        std::cin >> src >> dest >> d;
        directed_graph[src].push_back(dest);
        value[dest] = d;
        parent[dest] = src;
    }
    std::cin.ignore(); // to ignore newline
    for(int m = 0; m < op; ++m) {
        std::string buf;
        std::getline(std::cin, buf);
        std::istringstream iss(buf);
        std::string s;

        std::getline(iss, s, ' ');
        // wonky stuff here Add will break if the directed_graph are suddenly disjointed
        if (s[0] == 'A') {
            std::getline(iss, s, ' ');
            int add_src = std::stoi(s);
            std::getline(iss, s, ' ');
            int add_dest = std::stoi(s);
            std::getline(iss, s, ' ');
            int add_d = std::stoi(s);
            directed_graph[add_src].push_back(add_dest);
            value[add_dest] = add_d;
            parent[add_dest] = add_src;
        } else if (buf[0] == 'C') {
            long long int max_value = std::numeric_limits<long long int>::min();
            long long int root_result = root;
            std::vector<long long int> prev_value = value; // copy the old value so it does not get deleted after runnign the algo
            FindMaximumPath(directed_graph, parent, value, max_value, root_result, root, -1);
            std::cout << "Maximum Value: " << max_value << '\n';
            std::cout << "Root of the Path: " << root_result << '\n';
            value = prev_value;
        } else {
            // Delete
            std::getline(iss, s, ' ');
            long long int node = std::stoi(s);
            long long int par = parent[node];
            if (node > 20005) {
                continue;
            }
            // This is a bit wonky as we did not delete parent -> child connection
            // but we deleted child -> parent connection
            for (auto child : directed_graph[node]) {
                directed_graph[par].push_back(child); // transfer children of node to parent
                parent[child] = par; // set parent of child as par
            }
            directed_graph[node].clear(); // delete current node's children
            // set parent to -1
            parent[node] = -1;
            // get 9/10 without setting it into negative
            value[node] = std::numeric_limits<long long int>::min(); // actually very important as a placeholder so this won't get count (it might break)
            // THIS IS A WORKAROUND as especially if we delete leaves, we technically do not delete leave,
            // we only set the leaf as 0 weight but DFS can still go
            // First sol : Set a really small number so the path does not every count (more than -100000 (the limit))
            // Second sol : Reiterate the parent node then delete the connection by maybe copying back and forth to the array (more legit solution)
        }
        iss.str("");
    }
    long long int max_value = std::numeric_limits<long long int>::min();
    long long int root_result = root;
    FindMaximumPath(directed_graph, parent, value, max_value, root_result, root, -1);
    std::cout << "Final Root: " << root_result << '\n';
}