把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF1535E Gold Transfer
题意：最初有一个点，有3e5次询问，每次询问都是在线的，不能先全部处理再输出总答案，询问有两种，第一种是加点：将第i个点加到目标点后面，每个点（包括第一个）都有一定数量的黄金和黄金价格，儿子节点的黄金价格一定比父亲贵；第二种是询问：当从根走到目标节点的路程中需要买w数量的黄金，求最后买到的黄金和最少需要花费多少钱（不过路上的黄金不够就全买）。

解：

在线加点很好做，甚至不需要树形结构，维护父亲就可以了。
根据父亲比儿子便宜的设定很容易想到贪心：从父亲节点开始一路走到目标节点，要么走到路上的黄金买完，要么走到自己需要的买完。但是这样的话每次去这么做复杂度就炸了——因为已经买完了的点还要去走一次，那么这题就变成了首先找到第一个还有黄金可买的点然后从那里开始一直往下买。
于是就变成了树上倍增的板子题，通过倍增的方式找到第一个剩余黄金不为0的点。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 300005
#define mdl 998244353
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
#define endl '\n'
using namespace std;
ll a[maxn], c[maxn], fa[maxn][20];
int main() {
    cfast;
    int q;
    cin >> q >> a[0] >> c[0];
    inc(i, 1, 20) {
        fa[0][i] = 0;
    }
    int tt = 0;
    while (q--) {
        tt++;
        int cmd;
        cin >> cmd;
        if (cmd == 1) {
            int p, ta, tc;
            cin >> p >> ta >> tc;
            a[tt] = ta;
            c[tt] = tc;
            inc(i, 1, 20) {
                if (i == 1)fa[tt][i] = p;
                else fa[tt][i] = fa[fa[tt][i - 1]][i - 1];
            }
        }
        else {
            int tar;
            ll w;
            ll gain = 0, price = 0;
            cin >> tar >> w;
            while (w > 0) {
                int tmp = tar;
                for (int i = 19; i >= 0; i--) {
                    if (a[fa[tmp][i]] > 0)tmp = fa[tmp][i];
                }
                if (w <= a[tmp]) {
                    gain += w;
                    a[tmp] -= w;
                    price += w * c[tmp];
                    w = 0;
                }
                else {
                    gain += a[tmp];                   
                    price += c[tmp] * a[tmp];
                    w -= a[tmp];
                    a[tmp] = 0;
                    
                }
                if (tmp == tar)break;
            }
            cout << gain << " " << price << endl;
            cout.flush();
        }
    }
}
//2022.4.19 13:14
/*



*/