火花

Posted on Edited on In

题目大意:给定一棵树,有一些操作.每次操作都是指定一个节点,然后有一个权值k,如果k大于指定节点连的出边,则继续延伸,依次类推,每延伸一条边就加上其贡献.多次在线询问.

暴力.

对每个节点都预处理一下,然后就可以搞出自己以及自己子树内的最大的边权值.顺便求一下权值和就可以了.

对于fa[i] = 1的情况,用前缀和数组和二分查找可做

对于fa[i] = i-1的情况,前缀和后缀和后缀最大值维护一下可做

详见代码:

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const int N = 3e5 + 66, mod = 1 << 20;

int ver[N << 1], nex[N << 1], len[N << 1], head[N], cnt;

inline void add_edge(int x, int y, int z)
{
    ver[++ cnt] = y;
    nex[cnt] = head[x];
    len[cnt] = z;
    return (void)(head[x] = cnt);
}

int T, n, q, res;
int val[N], maxv[N];

inline void dfs(int x)
{
    int i, y;
    for (i = head[x]; i; i = nex[i])
    {
        y = ver[i];
        dfs(y);
        maxv[x] = max(maxv[x], max(len[i], maxv[y]));
        val[x] += len[i] + val[y];
    }
    return;
}

inline void func(int x, int v)
{
    if (v >= maxv[x]) return (void)(res += val[x]);
    int i, y;
    for (i = head[x]; i; i = nex[i])
    {
        y = ver[i];
        if (len[i] > v) continue;
        res += len[i];
        func(y, v);
    }
    return;
}

int num, cnm[N], sum[N], sam[N];

inline void func1()
{
    int i, x, z, pos; q = read();
    sort(cnm + 1, cnm + 1 + num);
    for (i = 1; i <= num; ++ i) sum[i] = sum[i - 1] + cnm[i];
    while (q --)
    {
        x = read(), z = read();
        if (T) x = x ^ (res % mod), z = z ^ (res % mod);
        if (x != 1) put(0), res = 0;
        else
        {
            pos = upper_bound(cnm + 1, cnm + 1 + num, z) - cnm;
            res = sum[pos - 1] - sum[1 - 1];
            put(res);
        }
    }
    return;
}

inline void func2()
{
    int i, x, z, pos; q = read();
    for (i = num; i >= 1; -- i) maxv[i] = max(maxv[i + 1], cnm[i]), sam[i] = sam[i + 1] + cnm[i]; 
    for (i = 1; i <= num; ++ i) sum[i] = sum[i - 1] + cnm[i];

    while (q --)
    {
        x = read(), z = read();
        if (T) x = x ^ (res % mod), z = z ^ (res % mod);
        if (x == n) put(0), res = 0;
        else
        {
            if (z >= maxv[x]) put(sam[x]), res = sam[x];
            else
            {
                pos = x;
                while (z >= cnm[pos]) ++ pos; -- pos;
//				cout << "pos--->" << pos << '\n';
                res = sum[pos] - sum[x - 1];
                put(res);
            }
        }
    }
    return;
}

signed main()
{
    int i = read(), x, y, z, pd(0), sb(0);
    n = read(), T = read();
    for (i = 2; i <= n; ++ i)
    {
        y = read(), z = read();
        cnm[++ num] = z;
        add_edge(y, i, z);
        if (y != 1) pd = 1;
        if (y != i - 1) sb = 1;
    }
if (! pd)
{
    func1();
    return 0;
}
if (! sb)
{
    func2();
    return 0;
}
    dfs(1);
    q = read();
    while (q --)
    {
        x = read(), z = read();
        if (T) x = x ^ (res % mod), z = z ^ (res % mod);
        res = 0;
        func(x, z);
        put(res);
    }

    return 0;
}

后记:

第一次暴力压正解

跑的比正解都快,开心!

运气吧