DS HW3

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> a(100001);
vector<int> val(100001),pre(100001);
long long ans,level;
long long dfs(int i){
    if(a[i].size()==0){
        if(val[i]>ans){
            ans=val[i];
            level=i;
        }
        return val[i];
    }
    long long big1=0,big2=0,temp=0;
    for(int j:a[i]){
        temp=dfs(j);
        if(big1<temp||big2<temp) if(big1<big2) big1=temp; else big2=temp;
    }
    if(big1+big2+val[i]>ans) ans=big1+big2+val[i],level=i;
    return max(big1,big2)+val[i];
}
int main(){
    int n,t,x,y,z,head;
    cin>>n>>t;
    cin>>head>>y;
    val[head]=y;
    pre[head]=-1;
    while(n--){
        cin>>x>>y>>z;
        pre[y]=x;
        a[x].emplace_back(y);
        val[y]=z;
    }
    string s;
    while(t--){
        cin>>s;
        if(s=="Check"){
            ans=-9223372036854775808;
            if(a[head].size()>0) dfs(head); else ans=val[head];
            cout<<"Maximum Value: "<<ans<<"\nRoot of the Path: "<<level<<'\n';
        }else if(s=="Add"){
            cin>>x>>y>>z;
            pre[y]=x;
            a[x].emplace_back(y);
            val[y]=z;
        }else if(s=="Delete"){
            cin>>y;
            x=pre[y];
            if(x<0) continue;
            for(auto t=a[x].begin();t<a[x].end();t++){
                if((*t)==y){
                    a[x].erase(t);
                    for(int i:a[y]){
                        a[x].emplace_back(i);
                        pre[i]=x;
                    }
                    break;
                }
            }
            a[y].clear();
            val[y]=0;
            pre[y]=0;
        }
    }
    ans=-9223372036854775808;
    dfs(head);
    cout<<"Final Root: "<<level<<'\n';
    return 0;
}
/*
CS2351_DS_24Spring_HW3
https://acm.cs.nthu.edu.tw/contest/2986/
NTHU OJ 14291 - Run Away!!
AC code
2024 April 28
*/