CF932D Tree

Posted on Edited on In Word count in article: 741 Reading time ≈ 3 mins.
我TM真的不知道怎么给标签。。。

CF932D Tree

题目大意：

  • 首先，我们有\(Q\)次操作
  • 操作\(1\)：在节点\(R\)下面再加一个权值为\(W\)的点
  • 操作\(2\)：询问从点\(X\)开始往上走，（每次遇到权值大于当前选过的最后一个点的点必定会选），问最多能选多少点

分析

我们可以很容易的发现，我们选中的点一定是一个单调不下降序列

那么就是说，我们可以稍微改动一下操作一，让每一条链都一定是单调不上升的（从根出发的链）

然后，我们每次加入的点必定不会是已经存在的某个点的祖先，所以我们改变他的位置对原来的树是没有影响的

若有节点成为了这个被我们认为操作的节点的儿子，它的值依赖于我们人为操作的那个点，所以这个答案也不会因为我们的操作出现问题

那么我们就可以在加入节点的时候，找到第一个权值大于该节点的点做为这个点的父节点

顺便跟新一下前缀和

这个用倍增实现就好了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline void AddPoint(ll u, ll p)
{
    ll v = ++cnt;
    wight[v] = p;
    if (wight[u] >= wight[v]) {
        father[v][0] = u;
    } else {
        for (ll i = 19; ~i; --i)
            if (wight[father[u][i]] < wight[v])
                u = father[u][i];
        father[v][0] = father[u][0];
    }
    sum[v][0] = wight[father[v][0]]; 
    for (ll i = 1; i < 20; ++i) {
        father[v][i] = father[father[v][i - 1]][i - 1];
        if (sum[v][i - 1] < inf && father[v][i]) {
            sum[v][i] = sum[v][i - 1] + sum[father[v][i - 1]][i - 1];
        } else break;
    }
}

然后查询的话，能跳就跳，每次向上跳了更新一下限制即可

1
2
3
4
5
6
7
8
9
10
11
12
13
inline ll Query(ll x)
{
    if (wight[x] > limit) return 0;
    ll ans(1);
    limit -= wight[x];
    for (ll i = 19; ~i; --i)
        if (sum[x][i] <= limit) {
            ans += (1 << i);//向上跳了2的i次方层，那就有2的i次方个点
            limit -= sum[x][i];
            x = father[x][i];
        }
    return ans;
}

Code

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll maxn = 4e5 + 10;
const ll inf = 0x6f6f6f6f6f6f6f6f;

ll father[maxn][20], wight[maxn], cnt(1);
ll sum[maxn][20], lastans, limit;
ll Q, Opt, X, Y;

inline void AddPoint(ll u, ll p)
{
    ll v = ++cnt;
    wight[v] = p;
    if (wight[u] >= wight[v]) {
        father[v][0] = u;
    } else {
        for (ll i = 19; ~i; --i)
            if (wight[father[u][i]] < wight[v])
                u = father[u][i];
        father[v][0] = father[u][0];
    }
    sum[v][0] = wight[father[v][0]]; 
    for (ll i = 1; i < 20; ++i) {
        father[v][i] = father[father[v][i - 1]][i - 1];
        if (sum[v][i - 1] < inf && father[v][i]) {
            sum[v][i] = sum[v][i - 1] + sum[father[v][i - 1]][i - 1];
        } else break;
    }
}

inline ll Query(ll x)
{
    if (wight[x] > limit) return 0;
    ll ans(1);
    limit -= wight[x];
    for (ll i = 19; ~i; --i)
        if (sum[x][i] <= limit) {
            ans += (1 << i);
            limit -= sum[x][i];
            x = father[x][i];
        }
    return ans;
}

inline ll Read()
{
    ll x(0);
    char o(getchar());
    while (o < '0' || o > '9') o = getchar();
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x;
}

int main()
{
    memset (sum, 0x6f, sizeof sum);
    wight[0] = inf;
    Q = Read();
    while (Q--)
    {
        Opt = Read(), X = Read() ^ lastans, Y = Read() ^ lastans;
        if (Opt == 1) AddPoint(X, Y);
        else limit = Y, printf ("%lld\n", lastans = Query(X));
    }
    system("pause");
}