Educational Codeforces Round 110 (Rated for Div. 2)

E. Gold Transfer

简要思路

• 操作1: 将点加到树上，并且更新当前点的根结点的情况。
• 操作2: 通过使用倍增算法找到从当前点到根结点的路径中最接近根结点且黄金数目大于0的祖先结点。然后从祖先结点开始，往下依次获取黄金。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define fastIO() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define debug(x) std::cerr << #x << " " << (x) << endl
#define pb push_back
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define PF(x) ((x)*(x))
#define LF(x) ((x)*PF(x))
#define fu(i, mm, MM) for(int (i) = (mm); (i) <= (MM); ++(i))
#define fd(i, MM, mm) for(int (i) = (MM); (i) >= (mm); --(i))
#define eps 1e-6
double e_v = exp(1.0);
double pi_v = 4.0 * atan(1.0);
template<typename T = int>
inline T read() {
    T x = 0, w = 1; char c = getchar();
    while (c < '0' || c>'9') { if (c == '-') w = -1; c = getchar(); }
    while (c <= '9' && c >= '0') { x = (x << 1) + (x << 3) + c - '0'; c = getchar(); }
    return w == 1 ? x : -x;
}

const int N = 1e6 + 10;
int a[N], c[N], dp[N][25];
/**
 * 获取当前结点的离根结点最近的黄金数目不为0的祖先结点
 * */
int get_fa(int u) {
    fd(i, 20, 0) {
        if (a[dp[u][i]]) {
            u = dp[u][i];
        }
    }
    return u;
}
int main(int argc, char* argv[]) {
    fastIO();
    int n = read();
    a[0] = read();
    c[0] = read();
    fu(i, 1, n) {
        int op = read();
        if (op == 1) {
            dp[i][0] = read(), a[i] = read(), c[i] = read();
            fu(j, 1, 20) {
                dp[i][j] = dp[dp[i][j - 1]][j - 1];
            }
        } else if (op == 2) {
            int v = read(), w = read();
            ll ans1 = 0, ans2 = 0;
            while (a[v] && w) {
                int u = get_fa(v);
                int minV = min(a[u], w);
                w -= minV;
                a[u] -= minV;
                ans1 += minV;
                ans2 += 1LL * minV * c[u];
            }
            cout << ans1 << " " << ans2 << endl;
        }
    }
    return 0;
}