题目描述

算法1

(树形DP) $O(n)$

这题的困难版本要用到树链剖分 和 LCA 技术栈还没点到
心血来潮画两个热狗。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int  N = 2E5 + 10;
int maxx[N],minn[N];
int dpmax[N],dpmin[N];
int n,t;
char op;
int main(){
    cin >> t;
    while(t--){
        cin >> n;
        int cnt = 1;
        dpmax[1] = maxx[1] = minn[1] = 1;
        dpmin[1] = 0;
        while(n--){
            cin >> op;
            if(op == '+'){
                cnt++;
                int v,x;
                cin >> v >> x;
                maxx[cnt] = max(x,x+maxx[v]);//只选这个 还是 选这个加上面那个 （子链的连续性） 这两种选择包含所有的情况 即是否继承上面
                dpmax[cnt] = max(dpmax[v],maxx[cnt]);//选这个 还是 不选这个
                minn[cnt] = min(x,x+minn[v]);//只选这个 还是 选这个加上面那个 （子链的连续性）
                dpmin[cnt] = min(dpmin[v],minn[cnt]);
            }else{
                int a,b,k;
                cin >> a >> b >> k;
                if(dpmax[b] >= k && dpmin[b] <= k){
                    cout <<"YES"<<endl;
                }else{
                    cout <<"NO"<<endl;
                }
            }
        }



    }



    return 0;
}