树上问题总结

2015.12.30 09:43 Wed| 27 visits oi_2016| 2016_刷题日常| Text

SPOJQTREE Query on a tree

每一次改变边权或查询两点间边权最大值。可以将边权下放到点权,之后利用树链剖分维护。

  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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <bits/stdc++.h>
using namespace std;

#define N 10005
#define lson (pos << 1)
#define rson (pos << 1 | 1)

int test, n, x[N], y[N], z[N], head[N], cnt;
int fa[N], deep[N], size[N], son[N], top[N];
int tot, id[N], id2[N], p[N], maxc[N * 4];
char opt[10];

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[N * 2];

inline void add(int x, int y)
{
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void dfs(int x)
{
    size[x] = 1; deep[x] = deep[fa[x]] + 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa[x])
        {
            fa[edge[i].to] = x, dfs(edge[i].to);
            size[x] += size[edge[i].to];
            if (size[edge[i].to] > size[son[x]])
                son[x] = edge[i].to;
        }
}

void create(int x, int d)
{
    id[x] = ++tot, p[tot] = x;
    top[x] = d;
    if (son[x]) create(son[x], d);
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa[x] && edge[i].to != son[x])
            create(edge[i].to, edge[i].to);
    id2[x] = tot;
}

void modify(int pos, int l, int r, int x, int y)
{
    if (l == r) { maxc[pos] = y; return; }
    int mid = (l + r) >> 1;
    if (x <= mid) modify(lson, l, mid, x, y);
    else modify(rson, mid + 1, r, x, y);
    maxc[pos] = max(maxc[lson], maxc[rson]);
}

int query(int pos, int l, int r, int x, int y)
{
    if (x <= l && r <= y) return maxc[pos];
    int mid = (l + r) >> 1;
    if (y <= mid) return query(lson, l, mid, x, y);
    if (x > mid) return query(rson, mid + 1, r, x, y);
    return max(query(lson, l, mid, x, y),
               query(rson, mid + 1, r, x, y));
}

int lca(int x, int y)
{
    int f1 = top[x], f2 = top[y];
    while (f1 != f2)
    {
        if (deep[f1] < deep[f2])
            swap(x, y), swap(f1, f2);
        x = fa[f1], f1 = top[x];
    }
    if (deep[x] > deep[y]) swap(x, y);
    return x;
}

int getmax(int x, int p)
{
    int f1 = top[x], f2 = top[p], re = 0;
    while (f1 != f2)
    {
        re = max(re, query(1, 1, n, id[f1], id[x]));
        x = fa[f1], f1 = top[x];
    }
    if (x != p)
        re = max(re, query(1, 1, n, id[p] + 1, id[x]));
    return re;
}

void init()
{
    cnt = 1; tot = 0;
    memset(head, 0, sizeof head);
    memset(fa, 0, sizeof fa);
    memset(deep, 0, sizeof deep);
    memset(size, 0, sizeof size);
    memset(son, 0, sizeof son);
    memset(top, 0, sizeof top);
    memset(id, 0, sizeof id);
    memset(p, 0, sizeof p);
    memset(maxc, 0, sizeof maxc);
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> test;
    while (test--)
    {
        init();
        cin >> n;
        for (int i = 1; i < n; ++i)
            x[i] = read(), y[i] = read(), z[i] = read(),
            add(x[i], y[i]), add(y[i], x[i]);
        dfs(1); create(1, 1);
        for (int i = 1; i < n; ++i)
        {
            if (deep[x[i]] < deep[y[i]])
                swap(x[i], y[i]);
            modify(1, 1, n, id[x[i]], z[i]);
        }
        while (scanf("%s", opt), opt[0] != 'D')
        {
            int a = read(), b = read(), t;
            if (opt[0] == 'C')
                modify(1, 1, n, id[x[a]], b);
            else
                t = lca(a, b),
                printf("%d\n", max(getmax(a, t), getmax(b, t)));
        }
    }
    return 0;
}

SPOJQTREE2 Query on a tree II

用倍增求 LCA 和路径上的第 k 个点就好了,然而要注意路径上的第 i 个点是点 x 的第 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
#include <bits/stdc++.h>
using namespace std;

#define N 10005

int test, n, head[N], cnt;
int fa[N][16], deep[N], dist[N];
char opt[10];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 2];

inline void add(int x, int y, int z)
{
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

void dfs(int x)
{
    deep[x] = deep[fa[x][0]] + 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa[x][0])
            dist[edge[i].to] = dist[x] + edge[i].val,
            fa[edge[i].to][0] = x, dfs(edge[i].to);
}

int lca(int x, int y)
{
    if (deep[x] < deep[y]) swap(x, y);
    for (int i = 15; i >= 0; --i)
        if (deep[fa[x][i]] >= deep[y])
            x = fa[x][i];
    if (x == y) return x;
    for (int i = 15; i >= 0; --i)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

int getfa(int x, int k)
{
    for (int i = 15; i >= 0; --i)
        if (k & (1 << i))
            x = fa[x][i];
    return x;
}

void init()
{
    cnt = 1;
    memset(head, 0, sizeof head);
    memset(fa, 0, sizeof fa);
    memset(deep, 0, sizeof deep);
    memset(dist, 0, sizeof dist);
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> test;
    while (test--)
    {
        init();
        cin >> n;
        for (int x, y, z, i = 1; i < n; ++i)
            x = read(), y = read(), z = read(),
            add(x, y, z), add(y, x, z);
        dfs(1);
        for (int j = 1; j <= 15; ++j)
            for (int i = 1; i <= n; ++i)
                fa[i][j] = fa[fa[i][j - 1]][j - 1];
        while (scanf("%s", opt), opt[1] != 'O')
        {
            if (opt[0] == 'D')
            {
                int x = read(), y = read();
                printf("%d\n", dist[x] + dist[y] - 2 * dist[lca(x, y)]);
            }
            else
            {
                int x = read(), y = read(), z = read();
                int p = lca(x, y);
                if (z <= deep[x] - deep[p] + 1)
                    printf("%d\n", getfa(x, z - 1));
                else
                    z = deep[x] + deep[y] - 2 * deep[p] - z + 1,
                    printf("%d\n", getfa(y, z));
            }
        }
        puts("");
    }
    return 0;
}

SPOJPT07J Query on a tree III

子树修改,搞出来 DFS 序之后就可以上主席树了。

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

#define N 100005

int n, q, a[N], head[N], id[N], id2[N], p[N];
vector<int> v;

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[N * 2];

inline void add(int x, int y)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void dfs(int x)
{
    static int tot = 0;
    id[x] = ++tot, p[tot] = x;
    for (int i = head[x]; i; i = edge[i].next)
        if (!id[edge[i].to]) dfs(edge[i].to);
    id2[x] = tot;
}

struct node
{
    node *son[2]; int size, p;
    void *operator new(size_t s);
} newnode[2000005];

void *node::operator new(size_t s)
{
    static node *p = newnode;
    return p++;
}

node *root[N];

void insert(node *pre, node *&pos, int l, int r, int x, int y)
{
    pos = new node(); *pos = *pre;
    ++pos->size;
    if (l == r) { pos->p = y; return; }
    int mid = (l + r) >> 1;
    if (x <= mid) insert(pre->son[0], pos->son[0], l, mid, x, y);
    else insert(pre->son[1], pos->son[1], mid + 1, r, x, y);
}

int query(node *pre, node *pos, int l, int r, int x)
{
    if (l == r) return pos->p;
    int mid = (l + r) >> 1, t = pos->son[0]->size - pre->son[0]->size;
    if (x <= t)
        return query(pre->son[0], pos->son[0], l, mid, x);
    else
        return query(pre->son[1], pos->son[1], mid + 1, r, x - t);
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        a[i] = read(), v.push_back(a[i]);
    sort(v.begin(), v.end());
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
    for (int x, y, i = 1; i < n; ++i)
        x = read(), y = read(), add(x, y), add(y, x);
    dfs(1);
    root[0] = new node();
    root[0]->son[0] = root[0]->son[1] = root[0];
    for (int i = 1; i <= n; ++i)
        insert(root[i - 1], root[i], 1, n, a[p[i]], p[i]);
    cin >> q;
    for (int i = 1; i <= q; ++i)
    {
        int x = read(), k = read();
        printf("%d\n", query(root[id[x] - 1], root[id2[x]], 1, n, k));
    }
    return 0;
}

POJ1741 Tree

树分治。对于每一个分治中心,可以先加上总答案,再减去在每一棵子树里多算的答案,这样竟然会减少代码量。

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

#define N 10005
#define inf 0x3f3f3f3f

int n, m, head[N], cnt, vis[N], size[N], maxs[N], dist[N];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 2];

inline void add(int x, int y, int z)
{
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

int root;

void findroot(int sum, int x, int fa)
{
    size[x] = 1; maxs[x] = 0;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            findroot(sum, edge[i].to, x),
            size[x] += size[edge[i].to],
            maxs[x] = max(maxs[x], size[edge[i].to]);
    maxs[x] = max(maxs[x], sum - size[x]);
    if (maxs[x] < maxs[root]) root = x;
}

void getdist(int x, int fa, vector<int> &v)
{
    v.push_back(dist[x]);
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            dist[edge[i].to] = dist[x] + edge[i].val,
            getdist(edge[i].to, x, v);
}

int getans(int d, int x)
{
    static vector<int> v;
    v.resize(0);
    dist[x] = d, getdist(x, 0, v);
    sort(v.begin(), v.end());
    int re = 0, l = 0, r = v.size() - 1;
    while (l < r)
        if (v[l] + v[r] <= m) re += r - l, ++l;
        else --r;
    return re;
}

int solve(int x)
{
    vis[x] = 1;
    int re = getans(0, x);
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to])
            re -= getans(edge[i].val, edge[i].to),
            root = 0, findroot(size[edge[i].to], edge[i].to, 0),
            re += solve(root);
    return re;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void init()
{
    cnt = 1;
    memset(head, 0, sizeof head);
    memset(vis, 0, sizeof vis);
}

int main()
{
    while (cin >> n >> m, n)
    {
        init();
        for (int x, y, z, i = 1; i < n; ++i)
            x = read(), y = read(), z = read(), add(x, y, z), add(y, x, z);
        maxs[0] = inf;
        root = 0, findroot(n, 1, 0);
        cout << solve(root) << endl;
    }
    return 0;
}

BZOJ1095 [ZJOI2007]Hide 捉迷藏

pb_ds的使用说明。

其实我的姿势并不好,当询问数量比较多的时候慢得要死。

然而果然比大爷快得多。

  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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>

using namespace std;
using namespace __gnu_pbds;

#define N 100005
#define inf 0x3f3f3f3f

__gnu_pbds::priority_queue<int> q1, q3[N];
__gnu_pbds::priority_queue<pair<int, int> > q2[N];
__gnu_pbds::priority_queue<int>::point_iterator pos1[N];
vector<__gnu_pbds::priority_queue<pair<int, int> >::point_iterator> pos2[N];
vector<__gnu_pbds::priority_queue<int>::point_iterator> pos3[N];

int n, m, head[N], size[N], maxs[N], vis[N], id[N], fa[N], num[N], open[N];
vector<int> mp[N]; char opt[10];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 2];

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

int root;

void dfs(int x, int fa)
{
    size[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            dfs(edge[i].to, x), size[x] += size[edge[i].to];
}

void getroot(int n, int x, int fa)
{
    size[x] = 1; maxs[x] = 0;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            getroot(n, edge[i].to, x),
            size[x] += size[edge[i].to],
            maxs[x] = max(maxs[x], size[edge[i].to]);
    maxs[x] = max(maxs[x], n - size[x]);
    if (maxs[x] < maxs[root]) root = x;
}

void getdist(int p, int x, int fa, int d)
{
    mp[p][id[x] - id[p]] = d;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            getdist(p, edge[i].to, x, d + edge[i].val);
}

void build(int x)
{
    static int tot = 0;
    id[x] = ++tot; vis[x] = 1;
    dfs(x, 0);
    mp[x].resize(size[x]), pos3[x].resize(size[x]);
    int son = 0;
    pos2[x].push_back(q2[x].push(make_pair(-1, son++)));
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to])
        {
            root = 0, getroot(size[edge[i].to], edge[i].to, 0);
            fa[root] = x, num[root] = son;
            pos2[x].push_back(q2[x].push(make_pair(-1, son++)));
            build(root);
        }
    getdist(x, x, 0, 0);
    vis[x] = 0;
}

void turnon(int x)
{
    q2[x].modify(pos2[x][0], make_pair(0, 0));
    for (int i = x; fa[i]; i = fa[i])
    {
        pos3[i][id[x] - id[i]] = q3[i].push(mp[fa[i]][id[x] - id[fa[i]]]);
        q2[fa[i]].modify(pos2[fa[i]][num[i]], make_pair(q3[i].top(), num[i]));
    }
    for (int i = x; i; i = fa[i])
    {
        pair<int, int> t = q2[i].top(); q2[i].pop();
        if (!q2[i].empty() && q2[i].top().first != -1)
            q1.modify(pos1[i], t.first + q2[i].top().first);
        else q1.modify(pos1[i], -1);
        pos2[i][t.second] = q2[i].push(t);
    }
}

void turnoff(int x)
{
    q2[x].modify(pos2[x][0], make_pair(-1, 0));
    for (int i = x; fa[i]; i = fa[i])
    {
        q3[i].erase(pos3[i][id[x] - id[i]]);
        if (q3[i].empty())
            q2[fa[i]].modify(pos2[fa[i]][num[i]], make_pair(-1, num[i]));
        else
            q2[fa[i]].modify(pos2[fa[i]][num[i]], make_pair(q3[i].top(), num[i]));
    }
    for (int i = x; i; i = fa[i])
    {
        pair<int, int> t = q2[i].top(); q2[i].pop();
        if (!q2[i].empty() && q2[i].top().first != -1)
            q1.modify(pos1[i], t.first + q2[i].top().first);
        else q1.modify(pos1[i], -1);
        pos2[i][t.second] = q2[i].push(t);
    }
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n;
    for (int x, y, i = 1; i < n; ++i)
        x = read(), y = read(),
        add(x, y, 1), add(y, x, 1);
    maxs[0] = inf;
    root = 0, getroot(n, 1, 0);
    build(root);
    for (int i = 1; i <= n; ++i)
        pos1[i] = q1.push(-1);
    for (int i = 1; i <= n; ++i)
        open[i] = 1, turnon(i);
    cin >> m;
    while (m--)
    {
        scanf("%s", opt);
        if (opt[0] == 'G')
        {
            printf("%d\n", q1.top());
        }
        else
        {
            int x = read();
            open[x] ? turnoff(x) : turnon(x);
            open[x] = !open[x];
        }
    }
    return 0;
}

HDU5571 tree

在求重心的时候,我认为我们需要粘模板(不要忘记重要的事情啊,每一次递归要清两个东西啊),重心求不好会 MLE 啊。

  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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <bits/stdc++.h>
using namespace std;

#define N 30005

int n, m, a[N], b[N], c[N], head[N], cnt, tot, val[N];
int vis[N], id[N], fa[N], size[N], maxs[N], num[N][2];
long long ans, sum[N][2], sumf[N][2], result[N];
vector<int> mp[N];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 2];

inline void add(int x, int y, int z)
{
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

int root;

void getroot(int sum, int x, int fa)
{
    size[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            getroot(sum, edge[i].to, x),
            size[x] += size[edge[i].to],
            maxs[x] = max(maxs[x], size[edge[i].to]);
    maxs[x] = max(maxs[x], sum - size[x]);
    if (maxs[x] < maxs[root]) root = x;
}

void dfs(int x, int fa)
{
    size[x] = 1; maxs[x] = 0;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            dfs(edge[i].to, x),
            size[x] += size[edge[i].to];
}

void getdist(int p, int x, int fa, int d)
{
    mp[p][id[x] - id[p]] = d;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            getdist(p, edge[i].to, x, d + edge[i].val);
}

void build(int x)
{
    id[x] = ++tot;
    dfs(x, 0); vis[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to])
        {
            root = 0, getroot(size[edge[i].to], edge[i].to, 0);
            fa[root] = x, build(root);
        }
    mp[x].clear();
    mp[x].resize(size[x]);
    getdist(x, x, 0, 0);
    num[x][0] = size[x];
    for (int i = 0; i < size[x]; ++i)
        sum[x][0] += mp[x][i];
    vis[x] = 0;
}

void turn(int x, int d)
{
    ans += sum[x][d], ans -= sum[x][d ^ 1];
    for (int i = x; fa[i]; i = fa[i])
    {
        ans += sum[fa[i]][d];
        ans += 1ll * num[fa[i]][d] * mp[fa[i]][id[x] - id[fa[i]]];
        ans -= sum[fa[i]][d ^ 1];
        ans -= 1ll * num[fa[i]][d ^ 1] * mp[fa[i]][id[x] - id[fa[i]]];
        ans -= sumf[i][d];
        ans -= 1ll * num[i][d] * mp[fa[i]][id[x] - id[fa[i]]];
        ans += sumf[i][d ^ 1];
        ans += 1ll * num[i][d ^ 1] * mp[fa[i]][id[x] - id[fa[i]]];
    }
    for (int i = x; i; i = fa[i])
    {
        --num[i][d], ++num[i][d ^ 1];
        sum[i][d] -= mp[i][id[x] - id[i]];
        sum[i][d ^ 1] += mp[i][id[x] - id[i]];
    }
    for (int i = x; fa[i]; i = fa[i])
    {
        sumf[i][d] -= mp[fa[i]][id[x] - id[fa[i]]];
        sumf[i][d ^ 1] += mp[fa[i]][id[x] - id[fa[i]]];
    }
}

void change(int x, int y)
{
    if (val[x] == y) return;
    turn(x, val[x]);
    val[x] ^= 1;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void init()
{
    cnt = 0; tot = 0; ans = 0;
    memset(head, 0, sizeof head);
    memset(result, 0, sizeof result);
    memset(val, 0, sizeof val);
    memset(vis, 0, sizeof vis);
    memset(id, 0, sizeof id);
    memset(fa, 0, sizeof fa);
    memset(size, 0, sizeof size);
    memset(maxs, 0, sizeof maxs);
    memset(num, 0, sizeof num);
    memset(sum, 0, sizeof sum);
    memset(sumf, 0, sizeof sumf);
}

int main()
{
    while (cin >> n)
    {
        init();
        for (int i = 1; i <= n; ++i)
            a[i] = read();
        for (int x, y, z, i = 1; i < n; ++i)
            x = read(), y = read(), z = read(),
            add(x, y, z), add(y, x, z);
        cin >> m;
        for (int i = 1; i <= m; ++i)
            b[i] = read(), c[i] = read();
        maxs[0] = 0x3f3f3f3f;
        root = 0, getroot(n, 1, 0);
        build(root);
        for (int x = 1; x <= n; ++x)
            for (int i = 0; fa[x] && i < size[x]; ++i)
                sumf[x][0] += mp[fa[x]][id[x] - id[fa[x]] + i];
        for (int bit = 1; bit < 16384; bit <<= 1)
        {
            for (int i = 1; i <= n; ++i)
                change(i, a[i] & bit ? 1 : 0);
            for (int i = 1; i <= m; ++i)
                change(b[i], c[i] & bit ? 1 : 0),
                result[i] += ans * bit;
        }
        for (int i = 1; i <= m; ++i)
            printf("%lld\n", result[i]);
    }
    return 0;
}

POJ3237 Tree

和 QTREE1 相比多了一个反转的操作,在线段树上维护一个最小值就好了。

  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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include <bits/stdc++.h>
using namespace std;

#define N 10005
#define lson (pos << 1)
#define rson (pos << 1 | 1)

int test, n, x[N], y[N], z[N], head[N], cnt;
int fa[N], deep[N], size[N], son[N], top[N];
int tot, id[N], id2[N], p[N], maxc[N * 4], minc[N * 4], tag[N * 4];
char opt[10];

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[N * 2];

inline void add(int x, int y)
{
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void dfs(int x)
{
    size[x] = 1; deep[x] = deep[fa[x]] + 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa[x])
        {
            fa[edge[i].to] = x, dfs(edge[i].to);
            size[x] += size[edge[i].to];
            if (size[edge[i].to] > size[son[x]])
                son[x] = edge[i].to;
        }
}

void create(int x, int d)
{
    id[x] = ++tot, p[tot] = x;
    top[x] = d;
    if (son[x]) create(son[x], d);
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa[x] && edge[i].to != son[x])
            create(edge[i].to, edge[i].to);
    id2[x] = tot;
}

void lazy(int pos)
{
    tag[pos] = 0; tag[lson] ^= 1, tag[rson] ^= 1;
    swap(maxc[lson], minc[lson]);
    maxc[lson] = -maxc[lson], minc[lson] = -minc[lson];
    swap(maxc[rson], minc[rson]);
    maxc[rson] = -maxc[rson], minc[rson] = -minc[rson];
}

void modify(int pos, int l, int r, int x, int y)
{
    if (l == r) { maxc[pos] = minc[pos] = y; return; }
    if (tag[pos]) lazy(pos);
    int mid = (l + r) >> 1;
    if (x <= mid) modify(lson, l, mid, x, y);
    else modify(rson, mid + 1, r, x, y);
    maxc[pos] = max(maxc[lson], maxc[rson]);
    minc[pos] = min(minc[lson], minc[rson]);
}

void change(int pos, int l , int r, int x, int y)
{
    if (x <= l && r <= y)
    {
        tag[pos] ^= 1; swap(maxc[pos], minc[pos]);
        maxc[pos] = -maxc[pos], minc[pos] = -minc[pos]; return;
    }
    if (tag[pos]) lazy(pos);
    int mid = (l + r) >> 1;
    if (x <= mid) change(lson, l, mid, x, y);
    if (y > mid) change(rson, mid + 1, r, x, y);
    maxc[pos] = max(maxc[lson], maxc[rson]);
    minc[pos] = min(minc[lson], minc[rson]);
}

int query(int pos, int l, int r, int x, int y)
{
    if (x <= l && r <= y) return maxc[pos];
    if (tag[pos]) lazy(pos);
    int mid = (l + r) >> 1;
    if (y <= mid) return query(lson, l, mid, x, y);
    if (x > mid) return query(rson, mid + 1, r, x, y);
    return max(query(lson, l, mid, x, y),
               query(rson, mid + 1, r, x, y));
}

int lca(int x, int y)
{
    int f1 = top[x], f2 = top[y];
    while (f1 != f2)
    {
        if (deep[f1] < deep[f2])
            swap(x, y), swap(f1, f2);
        x = fa[f1], f1 = top[x];
    }
    if (deep[x] > deep[y]) swap(x, y);
    return x;
}

void flip(int x, int p)
{
    int f1 = top[x], f2 = top[p];
    while (f1 != f2)
    {
        change(1, 1, n, id[f1], id[x]);
        x = fa[f1], f1 = top[x];
    }
    if (x != p)
        change(1, 1, n, id[p] + 1, id[x]);
}

int getmax(int x, int p)
{
    int f1 = top[x], f2 = top[p], re = 0xc0c0c0c0;
    while (f1 != f2)
    {
        re = max(re, query(1, 1, n, id[f1], id[x]));
        x = fa[f1], f1 = top[x];
    }
    if (x != p)
        re = max(re, query(1, 1, n, id[p] + 1, id[x]));
    return re;
}

void init()
{
    cnt = 1; tot = 0;
    memset(head, 0, sizeof head);
    memset(fa, 0, sizeof fa);
    memset(deep, 0, sizeof deep);
    memset(size, 0, sizeof size);
    memset(son, 0, sizeof son);
    memset(top, 0, sizeof top);
    memset(id, 0, sizeof id);
    memset(p, 0, sizeof p);
    memset(maxc, 0xc0, sizeof maxc);
    memset(minc, 0x3f, sizeof minc);
    memset(tag, 0, sizeof tag);
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> test;
    while (test--)
    {
        init();
        cin >> n;
        for (int i = 1; i < n; ++i)
            x[i] = read(), y[i] = read(), z[i] = read(),
            add(x[i], y[i]), add(y[i], x[i]);
        dfs(1); create(1, 1);
        for (int i = 1; i < n; ++i)
        {
            if (deep[x[i]] < deep[y[i]])
                swap(x[i], y[i]);
            modify(1, 1, n, id[x[i]], z[i]);
        }
        while (scanf("%s", opt), opt[0] != 'D')
        {
            int a = read(), b = read(), t;
            if (opt[0] == 'C')
                modify(1, 1, n, id[x[a]], b);
            else if (opt[0] == 'N')
                t = lca(a, b), flip(a, t), flip(b, t);
            else
                t = lca(a, b),
                printf("%d\n", max(getmax(a, t), getmax(b, t)));
        }
    }
    return 0;
}

POJ3321 Apple Tree

傻 X 题……评论区里面竟然有人说这题做了一个星期……

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

#define N 200005

int n, m, head[N], vis[N], id[N], id2[N], bit[N];

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[N * 2];

inline void add(int x, int y)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void insert(int x, int y)
{
    for (int i = x; i <= n; i += i & -i)
        bit[i] += y;
}

int query(int x)
{
    int re = 0;
    for (int i = x; i; i -= i & -i)
        re += bit[i];
    return re;
}

void dfs(int x, int fa = 0)
{
    static int tot = 0;
    id[x] = ++tot;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa)
            dfs(edge[i].to, x);
    id2[x] = tot;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n;
    for (int x, y, i = 1; i < n; ++i)
        x = read(), y = read(), add(x, y), add(y, x);
    dfs(1);
    for (int i = 1; i <= n; ++i)
        insert(i, vis[i] = 1);
    cin >> m;
    char opt[10]; int x;
    while (m--)
    {
        scanf("%s%d", opt, &x);
        if (opt[0] == 'Q')
            printf("%d\n", query(id2[x]) - query(id[x] - 1));
        else if (vis[x] == 1) insert(id[x], vis[x] = -1);
        else insert(id[x], vis[x] = 1);
    }
    return 0;
}

BZOJ3011 [Usaco2012 Dec]Running Away From the Barn

简单复习了一下可并堆。

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

struct heap
{
    struct node
    {
        static node *nil;
        node *son[2];
        long long key, tag; int npl, size;
        node() : npl(-1), size(0) {}
        node(long long _key)
        : key(_key), tag(0), npl(0), size(1) { son[0] = son[1] = nil; }
        void pushdown()
        {
            son[0]->key += tag; son[0]->tag += tag;
            son[1]->key += tag; son[1]->tag += tag; tag = 0;
        }
    };

    node *root;

    heap() { root = node::nil; }

    node *merge(node *x, node *y)
    {
        if (x == node::nil) return y;
        if (y == node::nil) return x;
        if (x->key < y->key) swap(x, y);
        x->pushdown();
        x->son[1] = merge(x->son[1], y);
        if (x->son[0]->npl < x->son[1]->npl)
            swap(x->son[0], x->son[1]);
        x->npl = x->son[1]->npl + 1;
        x->size = x->son[0]->size + x->son[1]->size + 1;
        return x;
    }
    bool empty() { return !root->size; }
    int size() { return root->size; }
    long long top() { return root->key; }
    void push(long long x) { node *t = new node(x); root = merge(root, t); }
    void pop() { root->pushdown(); root = merge(root->son[0], root->son[1]); }
    void insert(heap &h) { root = merge(root, h.root); h.root = node::nil; }
    void add(long long x) { root->key += x, root->tag = x; }
};

heap::node *heap::node::nil = new heap::node();

#define N 200005

int n, ans[N], head[N];
long long l;
heap q[N];

struct graph
{
    int next, to; long long val;
    graph() {}
    graph(int _next, int _to, long long _val)
    : next(_next), to(_to), val(_val) {}
} edge[N];

inline void add(int x, int y, long long z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

void dfs(int x)
{
    q[x].push(0);
    for (int i = head[x]; i; i = edge[i].next)
    {
        dfs(edge[i].to);
        q[edge[i].to].add(edge[i].val), q[x].insert(q[edge[i].to]);
    }
    while (q[x].size() && q[x].top() > l) q[x].pop();
    ans[x] = q[x].size();
}

inline long long read()
{
    long long x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> l;
    for (int x, i = 2; i <= n; ++i)
        x = read(), add(x, i, read());
    dfs(1);
    for (int i = 1; i <= n; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

BZOJ2051&4317 A Problem For Fun

树分治解法

对于每一个点的询问二分答案,再在从当前点到总分治中心的 log n 个分治子树中二分查询符合要求结点的个数,总时间复杂度为 O(nlog^3n)。

注意容斥的时候要减去的是当前分治中心的真正子树中的答案,而不是在分治时候重新构建出的子树中的答案 T^T 我是沙茶。

还有我竟然还在传 vector 去 lower_bound 的时候传了整个一个大 vector!!!这种脑残的小数据测不出来的错误以后要争取避免啊,不要妄自菲薄地高估 vector 的常数,它可是很快的~

然后 BZOJ4317 的话,如果把二分上界设成 100 是可以 AC 的。

  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
132
133
#include <bits/stdc++.h>
using namespace std;

#define N 50005

int n, k, head[N], size[N], maxs[N], vis[N], id[N], fa[N], tag[N];
vector<int> mp[N], son[N];
vector<vector<int> > v[N];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 2];

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

int root;

void getroot(int sum, int x, int fa)
{
    size[x] = 1, maxs[x] = 0;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            getroot(sum, edge[i].to, x),
            size[x] += size[edge[i].to],
            maxs[x] = max(maxs[x], size[edge[i].to]);
    maxs[x] = max(maxs[x], sum - size[x]);
    if (maxs[root] > maxs[x]) root = x;
}

void dfs(int x, int fa)
{
    size[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            dfs(edge[i].to, x),
            size[x] += size[edge[i].to];
}

void getdist(int p, int x, int fa, int d)
{
    mp[p][id[x] - id[p]] = d;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            getdist(p, edge[i].to, x, d + edge[i].val);
}

void dfs2(vector<int> &v, int x, int fa, int d)
{
    v.push_back(d);
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            dfs2(v, edge[i].to, x, d + edge[i].val);
}

void build(int x)
{
    static int tot = 0;
    id[x] = ++tot; vis[x] = 1;
    dfs(x, 0);
    int mad = 0;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to])
        {
            root = 0, getroot(size[edge[i].to], edge[i].to, 0);
            fa[root] = x, tag[root] = mad, build(root);
            v[x].resize(mad + 1);
            dfs2(v[x][mad], edge[i].to, x, edge[i].val);
            sort(v[x][mad].begin(), v[x][mad].end());
            ++mad;
        }
    mp[x].resize(size[x]);
    getdist(x, x, 0, 0);
    son[x].insert(son[x].end(), mp[x].begin(), mp[x].end());
    sort(son[x].begin(), son[x].end());
    vis[x] = 0;
}

inline int getnum(vector<int> &v, int len)
{
    if (len < 0) return 0;
    return upper_bound(v.begin(), v.end(), len) - v.begin();
}

int query(int x, int len)
{
    int re = getnum(son[x], len);
    for (int i = x; fa[i]; i = fa[i])
    {
        re += getnum(son[fa[i]], len - mp[fa[i]][id[x] - id[fa[i]]]);
        re -= getnum(v[fa[i]][tag[i]], len - mp[fa[i]][id[x] - id[fa[i]]]);
    }
    return re;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> k;
    for (int x, y, z, i = 1; i < n; ++i)
        x = read(), y = read(), z = read(),
        add(x, y, z), add(y, x, z);
    maxs[root] = 0x3f3f3f3f;
    root = 0; getroot(n, 1, 0);
    build(root);
    for (int i = 1; i <= n; ++i)
    {
        int l = 0, r = k * 10000, ans = 0;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (query(i, mid) <= k) l = mid + 1;
            else r = mid - 1, ans = mid;
        }
        printf("%d\n", ans);
    }
    return 0;
}

分块解法

vector 的常数真是好评呢,33s 就可以过 2051 了(宋爷和邢健开还在被卡着)。分块好写好调,令人无比省心的解法。

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

#define N 50005

int n, k, head[N], id[N], id2[N], a[N];
int bcnt, blo, bel[N], tag[N], ans[N];
vector<pair<int, int> > v[N];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 2];

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

void modify(int b, int l, int r, int t)
{
    static vector<pair<int, int> > v1, v2;
    v1.clear(), v2.clear();
    for (int i = 0; i < (int)v[b].size(); ++i)
        if (v[b][i].second >= l && v[b][i].second <= r)
            v1.push_back(make_pair(v[b][i].first + tag[b] - t, v[b][i].second));
        else
            v2.push_back(make_pair(v[b][i].first + tag[b] + t, v[b][i].second));
    tag[b] = 0, v[b].clear();
    int t1 = 0, t2 = 0;
    while (t1 < (int)v1.size() || t2 < (int)v2.size())
    {
        if (t2 >= (int)v2.size()) v[b].push_back(v1[t1++]);
        else if (t1 >= (int)v1.size()) v[b].push_back(v2[t2++]);
        else if (v1[t1] < v2[t2]) v[b].push_back(v1[t1++]);
        else v[b].push_back(v2[t2++]);
    }
}

void change(int l, int r, int t)
{
    for (int i = 1; i < bel[l]; ++i) tag[i] += t;
    for (int i = bel[l] + 1; i < bel[r]; ++i) tag[i] -= t;
    for (int i = bel[r] + 1; i <= bcnt; ++i) tag[i] += t;
    if (bel[l] == bel[r]) modify(bel[l], l, r, t);
    else modify(bel[l], l, r, t), modify(bel[r], l, r, t);
}

int query(int b, int mid)
{
    pair<int, int> t = make_pair(mid - tag[b], 0);
    return upper_bound(v[b].begin(), v[b].end(), t) - v[b].begin();
}

void dfs(int x, int d)
{
    static int tot = 0;
    id[x] = ++tot;
    a[id[x]] = d;
    for (int i = head[x]; i; i = edge[i].next)
        if (!id[edge[i].to])
            dfs(edge[i].to, d + edge[i].val);
    id2[x] = tot;
}

void getans(int x, int t)
{
    change(id[x], id2[x], t);
    int l = 0, r = k * 10000;
    while (l <= r)
    {
        int mid = (l + r) >> 1, temp = 0;
        for (int i = 1; i <= bcnt; ++i)
            temp += query(i, mid);
        if (temp <= k) ans[x] = mid, l = mid + 1;
        else r = mid - 1;
    }
    for (int i = head[x]; i; i = edge[i].next)
        if (id[edge[i].to] > id[x])
            getans(edge[i].to, edge[i].val);
    change(id[x], id2[x], -t);
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> k;
    for (int x, y, z, i = 1; i < n; ++i)
        x = read(), y = read(), z = read(),
        add(x, y, z), add(y, x, z);
    dfs(1, 0);
    bcnt = 0;
    blo = ceil(sqrt(n) * log2(n)) + 1;
    for (int i = 1; i <= n; ++i)
    {
        if (i % blo == 1) bel[i] = ++bcnt;
        else bel[i] = bcnt;
        v[bel[i]].push_back(make_pair(a[i], i));
    }
    for (int i = 1; i <= bcnt; ++i)
        sort(v[i].begin(), v[i].end());
    getans(1, 0);
    for (int i = 1; i <= n; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

BZOJ1146 [CTSC2008]网络管理Network

用入栈出栈序+主席树可以做到 O(n*log2n) 的时间复杂度。当然,我们需要离散化。当然,我们也可以不离散化。

  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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>
using namespace std;

#define N 80005
#define M 1000000

int n, q, a[N], head[N], deep[N], fa[N][18], id[N], id2[N];

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[N * 2];

inline void add(int x, int y)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

struct node
{
    node *son[2]; int size;
    node() : size(0) { son[0] = son[1] = NULL; }
    void *operator new(size_t s);
} np[12500000];

void *node::operator new(size_t s) { static node *p = np; return p++; }

node *root[N];
list<node *> l1, l2;

void insert(node *&pos, int l, int r, int x, int y)
{
    if (pos == NULL) pos = new node(); pos->size += y;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) insert(pos->son[0], l, mid, x, y);
    else insert(pos->son[1], mid + 1, r, x, y);
}

int queryk(list<node *> &p, list<node *> &m, int l, int r, int k)
{
    if (l == r) return l;
    int temp = 0;
    list<node *>::iterator i = p.begin();
    while (i != p.end())
        if (*i == NULL) i = p.erase(i);
        else if ((*i)->son[0]) temp += (*i)->son[0]->size, ++i;
        else ++i;
    i = m.begin();
    while (i != m.end())
        if (*i == NULL) i = m.erase(i);
        else if ((*i) && (*i)->son[0]) temp -= (*i)->son[0]->size, ++i;
        else ++i;
    int mid = (l + r) >> 1;
    if (temp >= k)
    {
        i = p.begin(); while (i != p.end()) (*i) = (*i)->son[0], ++i;
        i = m.begin(); while (i != m.end()) (*i) = (*i)->son[0], ++i;
        return queryk(p, m, l, mid, k);
    }
    else
    {
        i = p.begin(); while (i != p.end()) (*i) = (*i)->son[1], ++i;
        i = m.begin(); while (i != m.end()) (*i) = (*i)->son[1], ++i;
        return queryk(p, m, mid + 1, r, k - temp);
    }
}

void modify(int x, int y, int z)
{
    for (int i = x; i <= n; i += i & -i)
       insert(root[i], 1, M, y, z);
}

void query(list<node *> &l, int x)
{
    for (int i = x; i; i -= i & -i)
        l.push_back(root[i]);
}

void dfs(int x)
{
    static int tot = 0;
    id[x] = ++tot; deep[x] = deep[fa[x][0]] + 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa[x][0])
            fa[edge[i].to][0] = x, dfs(edge[i].to);
    id2[x] = tot + 1;
}

int lca(int x, int y)
{
    if (deep[x] < deep[y]) swap(x, y);
    for (int i = 17; i >= 0; --i)
        if (deep[fa[x][i]] >= deep[y])
            x = fa[x][i];
    if (x == y) return x;
    for (int i = 17; i >= 0; --i)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    for (int x, y, i = 1; i < n; ++i)
        x = read(), y = read(), add(x, y), add(y, x);
    dfs(1);
    for (int j = 1; j <= 17; ++j)
        for (int i = 1; i <= n; ++i)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    for (int i = 1; i <= n; ++i)
        modify(id[i], a[i], 1), modify(id2[i], a[i], -1);
    while (q--)
    {
        int k = read(), x = read(), y = read();
        if (k == 0)
        {
            modify(id[x], a[x], -1), modify(id2[x], a[x], 1);
            a[x] = y, modify(id[x], a[x], 1), modify(id2[x], a[x], -1);
        }
        else
        {
            int temp = lca(x, y);
            if (deep[x] + deep[y] - 2 * deep[temp] + 1 < k)
                { puts("invalid request!"); continue; }
            l1.clear(), l2.clear();
            query(l1, id[x]), query(l1, id[y]);
            query(l2, id[temp]), query(l2, id[fa[temp][0]]);
            printf("%d\n", queryk(l1, l2, 1, M, deep[x] + deep[y] - 2 * deep[temp] + 2 - k));
        }
    }
    return 0;
}

BZOJ2599 [IOI2011]Race

静态树分治加打标记,挺好写的?

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

#define N 200005
#define inf 0x3f3f3f3f

int n, k, ans, head[N], size[N], maxs[N], vis[N], step[N * 5], tag[N * 5];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 2];

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

int root = 0;

void getroot(int sum, int x, int fa)
{
    size[x] = 1, maxs[x] = 0;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            getroot(sum, edge[i].to, x),
            size[x] += size[edge[i].to],
            maxs[x] = max(maxs[x], size[edge[i].to]);
    maxs[x] = max(maxs[x], sum - size[x]);
    if (maxs[x] < maxs[root]) root = x;
}

void dfs(vector<pair<int, int> > &v, int x, int fa, int s, int d)
{
    if (d > k) return;
    v.push_back(make_pair(s, d));
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            dfs(v, edge[i].to, x, s + 1, d + edge[i].val);
}

void update(int p, int x, int d)
{
    static vector<pair<int, int> > v;
    v.resize(0);
    dfs(v, x, 0, 1, d);
    pair<int, int> i;
    for (int j = 0; j < (int)v.size(); ++j)
        if (i = v[j], tag[k - i.second] == p)
            ans = min(ans, step[k - i.second] + i.first);
    for (int j = 0; j < (int)v.size(); ++j)
        if (i = v[j], tag[i.second] != p || step[i.second] > i.first)
            tag[i.second] = p, step[i.second] = i.first;
}

void solve(int x)
{
    vis[x] = true;
    tag[0] = x, step[0] = 0;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to])
            update(x, edge[i].to, edge[i].val);
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to])
            root = 0, getroot(size[edge[i].to], edge[i].to, 0),
            solve(root);
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> k;
    for (int x, y, z, i = 1; i < n; ++i)
        x = read() + 1, y = read() + 1, z = read(),
        add(x, y, z), add(y, x, z);
    maxs[0] = inf; ans = inf;
    root = 0; getroot(n, 1, 0);
    solve(root);
    if (ans == inf) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}

BZOJ3124 [Sdoi2013]直径

这绝对是放上来恶心人的。对于每一个节点,我们需要记录从它出发的三条到子树的最长链、一条到父树的最长链,二个儿子中的最长链和它的父树中的最长链。转移?想想就刺激。

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

#define N 200005

int n, head[N], fe[N], ans;
long long dis[N], ff[N], fl[N], len;
vector<pair<long long, int> > fs[N], fz[N];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 2];

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

void dfs(int x, int fa)
{
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa)
            dis[edge[i].to] = dis[x] + edge[i].val,
            dfs(edge[i].to, x);
}

void predfs1(int x, int fa)
{
    for (int y, i = head[x]; i; i = edge[i].next)
        if ((y = edge[i].to) != fa)
            fe[y] = edge[i].val, predfs1(y, x),
            fs[x].push_back(make_pair(fs[y][0].first + edge[i].val, y)),
            fz[x].push_back(make_pair(max(fz[y][0].first,
                fs[y][0].first + fs[y][1].first), y));
    fs[x].push_back(make_pair(0, 0));
    fs[x].push_back(make_pair(0, 0));
    fs[x].push_back(make_pair(0, 0));
    fz[x].push_back(make_pair(0, 0));
    fz[x].push_back(make_pair(0, 0));
    sort(fs[x].begin(), fs[x].end()); reverse(fs[x].begin(), fs[x].end());
    sort(fz[x].begin(), fz[x].end()); reverse(fz[x].begin(), fz[x].end());
}

void predfs2(int x, int fa)
{
    if (x != 1)
    {   
        ff[x] = max(ff[fa], fs[fa][x == fs[fa][0].second].first) + fe[x];
        fl[x] = fl[fa];
        fl[x] = max(fl[x], fz[fa][x == fz[fa][0].second].first);
        fl[x] = max(fl[x], fs[fa][x == fs[fa][0].second].first + ff[fa]);
        if (x == fs[fa][0].second)
            fl[x] = max(fl[x], fs[fa][1].first + fs[fa][2].first);
        else if (x == fs[fa][1].second)
            fl[x] = max(fl[x], fs[fa][0].first + fs[fa][2].first);
        else
            fl[x] = max(fl[x], fs[fa][0].first + fs[fa][1].first);
    }
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa)
            predfs2(edge[i].to, x);
}

void getans(int x, int fa)
{
    if (fz[x][0].first != len &&
        fs[x][0].first + fs[x][1].first != len &&
        fl[x] != len)
        ++ans;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa)
            getans(edge[i].to, x);
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n;
    for (int x, y, z, i = 1; i < n; ++i)
        x = read(), y = read(), z = read(),
        add(x, y, z), add(y, x, z);
    dfs(1, 0); int s = 1;
    for (int i = 2; i <= n; ++i)
        if (dis[i] > dis[s]) s = i;
    memset(dis, 0, sizeof dis);
    dfs(s, 0);
    for (int i = 1; i <= n; ++i)
        len = max(len, dis[i]);
    cout << len << endl;
    predfs1(1, 0), predfs2(1, 0), getans(1, 0);
    cout << ans << endl;
    return 0;
}

BZOJ4326 NOIP2015 运输计划

树链的并什么的。我又用了一种污算法——把第一条链中的一个点当成根,然后每新加入一条链时只需要求两遍 LCA,判断一下深度就好了,于是在别的地方全都被卡常。

听说可以二分答案,传一传标记?

  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>
using namespace std;

#define N 300005

int n, m, x[N], y[N], cost[N], p[N];
int head[N], deep[N], fa[N][16], dis[N][16];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 2];

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

bool cmp(int x, int y)
{
    return cost[x] > cost[y];
}

void dfs(int x)
{
    deep[x] = deep[fa[x][0]] + 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa[x][0])
            fa[edge[i].to][0] = x,
            dis[edge[i].to][0] = edge[i].val,
            dfs(edge[i].to);
}

void getst(bool flag)
{
    for (int j = 1; j <= 15; ++j)
        for (int i = 1; i <= n; ++i)
            fa[i][j] = fa[fa[i][j - 1]][j - 1],
            dis[i][j] = flag ? dis[i][j - 1] + dis[fa[i][j - 1]][j - 1] :
                               max(dis[i][j - 1], dis[fa[i][j - 1]][j - 1]);
}

int lca(int x, int y)
{
    if (deep[x] < deep[y]) swap(x, y);
    for (int i = 15; i >= 0; --i)
        if (deep[fa[x][i]] >= deep[y])
            x = fa[x][i];
    if (x == y) return x;
    for (int i = 15; i >= 0; --i)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

int getdis(int x, int y)
{
    int re = 0;
    for (int i = 15; i >= 0; --i)
        if (deep[fa[x][i]] >= deep[y])
            re += dis[x][i], x = fa[x][i];
    return re;
}

int getval(int x, int y)
{
    int re = 0;
    for (int i = 15; i >= 0; --i)
        if (deep[fa[x][i]] >= deep[y])
            re = max(re, dis[x][i]), x = fa[x][i];
    return re;
}

char getc()
{
    static const int LEN = 1 << 15;
    static char buf[LEN], *S = buf, *T = buf;
    if (S == T)
    {
        T = (S = buf) + fread(buf, 1, LEN, stdin);
        if (S == T)return EOF;
    }
    return *S++;
}

inline int read()
{
    static char ch;
    static int D;
    while (!isdigit(ch = getc()));
    for (D = ch - '0'; isdigit(ch = getc());)
        D = (D << 3) + (D << 1) + (ch - '0');
    return D;
}

int main()
{
    n = read(), m = read();
    for (int x, y, z, i = 1; i < n; ++i)
        x = read(), y = read(), z = read(),
        add(x, y, z), add(y, x, z);
    dfs(1), getst(true);
    for (int t, i = 1; i <= m; ++i)
    {
        x[i] = read(), y[i] = read(), t = lca(x[i], y[i]);
        cost[i] = getdis(x[i], t) + getdis(y[i], t), p[i] = i;
    }
    sort(p + 1, p + m + 1, cmp);
    memset(fa, 0, sizeof fa);
    memset(dis, 0, sizeof dis);
    dfs(y[p[1]]), getst(false);
    int ans = cost[p[1]];
    int top = y[p[1]], low = x[p[1]];
    for (int i = 1; i <= m; ++i)
    {
        int t1 = lca(x[p[i]], low), t2 = lca(y[p[i]], low);
        if (deep[t1] < deep[top]) t1 = top;
        if (deep[t2] < deep[top]) t2 = top;
        if (t1 == t2) break;
        if (deep[t1] > deep[t2]) swap(t1, t2);
        top = t1, low = t2;
        ans = min(ans, max(cost[p[1]] - getval(low, top), cost[p[i + 1]]));
    }
    cout << ans << endl;
    return 0;
}

BZOJ3123 [Sdoi2013]森林

Count on tree 的基础上加入了连接操作,其实只需要启发式合并,每一次重构较小的树的父亲和可持久化线段树就好了。

然而在他告诉让连边的时候,不要忘记真的把那条边给连上啊……

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

#define N 80005

int n, m, t, a[N], head[N], bel[N], size[N], deep[N], fa[N][16];
vector<int> v;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[N * 2];

inline void add(int x, int y)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

struct node
{
    node *son[2]; int size;
    node() : size(0) { son[0] = son[1] = NULL; }
};

node *root[N];

void insert(node *pre, node *&pos, int l, int r, int x)
{
    pos = new node();
    *pos = *pre; ++pos->size;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) insert(pre->son[0], pos->son[0], l, mid, x);
    else insert(pre->son[1], pos->son[1], mid + 1, r, x);
}

int query(node *p1, node *p2, node *m1, node *m2, int l, int r, int k)
{
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int temp = p1->son[0]->size + p2->son[0]->size - m1->son[0]->size - m2->son[0]->size;
    if (k <= temp) return query(p1->son[0], p2->son[0], m1->son[0], m2->son[0], l, mid, k);
    else return query(p1->son[1], p2->son[1], m1->son[1], m2->son[1], mid + 1, r, k - temp);
}

void dfs(int p, int x)
{
    bel[x] = p, ++size[p];
    deep[x] = deep[fa[x][0]] + 1;
    for (int i = 1; i <= 15; ++i)
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    insert(root[fa[x][0]], root[x], 1, n, a[x]);
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa[x][0])
            fa[edge[i].to][0] = x, dfs(p, edge[i].to);
}

int lca(int x, int y)
{
    if (deep[x] < deep[y]) swap(x, y);
    for (int i = 15; i >= 0; --i)
        if (deep[fa[x][i]] >= deep[y])
            x = fa[x][i];
    if (x == y) return x;
    for (int i = 15; i >= 0; --i)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

void merge(int x, int y)
{
    if (size[bel[x]] < size[bel[y]]) swap(x, y);
    fa[y][0] = x, dfs(bel[x], y);
    add(x, y), add(y, x);
}

int getans(int x, int y, int z)
{
    int t = lca(x, y);
    return v[query(root[x], root[y], root[t], root[fa[t][0]], 1, n, z) - 1];
}

char str[10];

int main()
{
    cin.ignore(20, '\n');
    cin >> n >> m >> t;
    for (int i = 1; i <= n; ++i)
        a[i] = read(), v.push_back(a[i]);
    sort(v.begin(), v.end());
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
    for (int x, y, i = 1; i <= m; ++i)
        x = read(), y = read(), add(x, y), add(y, x);
    root[0] = new node();
    root[0]->son[0] = root[0]->son[1] = root[0];
    for (int i = 1; i <= n; ++i)
        if (!bel[i]) dfs(i, i);
    for (int x, y, z, lastans = 0, i = 1; i <= t; ++i)
    {
        scanf("%s", str);
        if (str[0] == 'Q')
            x = read() ^ lastans, y = read() ^ lastans, z = read() ^ lastans,
            printf("%d\n", lastans = getans(x, y, z));
        else
            x = read() ^ lastans, y = read() ^ lastans, merge(x, y);
    }
    return 0;
}

BZOJ3307 雨天的尾巴

BZOJ3672 [Noi2014]购票

首先推一下斜率优化的转移方程,需要对 p[i] = (d[i], dp[i]) 维护一个下凸壳,其中 d[i] 表示点 i 距离根节点的距离,dp[i] 表示从点 i 到根节点的最小花费。

然后,参考 PoPoQQQ 大爷的做法:

  1. 找到当前分治的树结构的重心;
  2. 将分成的子树中含有根节点那部分连重心一并分治;
  3. 将其余子树的点拎出来,按照能走到的最小深度从大到小排序;
  4. 对于每个点,将重心到分治结构的根节点路径上所有的点中能到达的那些点维护一个凸包,然后二分查找;
  5. 对其余子树进行分治。

注意第一步,我们需要找到的是距离根节点最近的重心,即保证重心的父亲所在的树的大小加上 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
#include <bits/stdc++.h>
using namespace std;

#define N 200005

int n, fa[N], head[N], vis[N], size[N], maxs[N];
long long d[N], p[N], q[N], l[N], dp[N];
vector<int> v;
deque<pair<long long, long long> > h;

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[N];

inline void add(int x, int y)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

inline bool cmp(int x, int y) { return l[x] < l[y]; }

void getroot(int &root, int sum, int x)
{
    size[x] = 1; maxs[x] = 0;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to])
            getroot(root, sum, edge[i].to),
            size[x] += size[edge[i].to],
            maxs[x] = max(maxs[x], size[edge[i].to]);
    maxs[x] = max(maxs[x], sum - size[x]);
    if (maxs[x] <= maxs[root]) root = x;
}

void getpoint(vector<int> &v, int x)
{
    v.push_back(x);
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to])
            getpoint(v, edge[i].to);
}

void solve(int top, int sum)
{
    if (sum == 1) return;
    int root = 0; getroot(root, sum, top);
    for (int i = head[root]; i; i = edge[i].next)
        vis[edge[i].to] = true;
    solve(top, sum - size[root] + 1);
    v.clear();
    h.clear();
    for (int i = head[root]; i; i = edge[i].next)
        getpoint(v, edge[i].to);
    sort(v.begin(), v.end(), cmp);
    while (v.size() && l[v.back()] > d[root]) v.pop_back();
    for (int i = root; i != fa[top]; i = fa[i])
    {
        while (h.size() > 1 &&
            1.0 * (h[1].second - h[0].second) / (h[1].first - h[0].first) <
            1.0 * (h[0].second - dp[i]) / (h[0].first - d[i])) h.pop_front();
        h.push_front(make_pair(d[i], dp[i]));
        while (v.size() && (i == top || l[v.back()] > d[fa[i]]))
        {
            int tl = 1, tr = h.size() - 1, ans = 0, now = v.back();
            while (tl <= tr)
            {
                int mid = (tl + tr) >> 1;
                if (1.0 * (h[mid].second - h[mid - 1].second) /
                          (h[mid].first - h[mid - 1].first) < 1.0 * p[now])
                    tl = mid + 1, ans = mid;
                else tr = mid - 1;
            }
            dp[now] = min(dp[now], h[ans].second +
                q[now] + p[now] * (d[now] - h[ans].first));
            v.pop_back();
        }
    }
    for (int i = head[root]; i; i = edge[i].next)
        solve(edge[i].to, size[edge[i].to]);
}

inline long long read()
{
    long long x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n; cin.ignore(20, '\n');
    for (int i = 2; i <= n; ++i)
    {
        add(fa[i] = read(), i), d[i] = d[fa[i]] + read(),
        p[i] = read(), q[i] = read(), l[i] = read();
        l[i] = max(d[i] - l[i], 0ll);
    }
    maxs[0] = 0x3f3f3f3f;
    memset(dp, 0x3f, sizeof dp);
    dp[0] = dp[1] = 0;
    solve(1, n);
    for (int i = 2; i <= n; ++i)
        printf("%lld\n", dp[i]);
    return 0;
}

BZOJ4012 [HNOI2015]开店

统计每一个分治结构中妖怪的每种年龄的数量、到分治中心的距离以及到上一层分治中心的距离,每个分治结构里将妖怪按照年龄排个序,二分前缀和就可以求答案了。当然,还是要处理每个点到每个包含它的分治结构的分治中心的距离。

  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
132
133
#include <bits/stdc++.h>
using namespace std;

#define N 150005

int n, q, a, head[N], age[N], size[N], maxs[N], vis[N], fa[N], id[N];
vector<pair<int, long long> > vn[N], vp[N];
vector<long long> dis[N];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 2];

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

void getroot(int &root, int sum, int x, int fa)
{
    size[x] = 1, maxs[x] = 0;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            getroot(root, sum, edge[i].to, x),
            size[x] += size[edge[i].to],
            maxs[x] = max(maxs[x], size[edge[i].to]);
    maxs[x] = max(maxs[x], sum - size[x]);
    if (maxs[x] <= maxs[root]) root = x;
}

void dfs(vector<pair<int, long long> > &v, int x, int fa, long long d)
{
    v.push_back(make_pair(age[x], d));
    size[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            dfs(v, edge[i].to, x, d + edge[i].val),
            size[x] += size[edge[i].to];
}

void getdis(int p, int x, int fa, long long d)
{
    dis[p][id[x] - id[p]] = d;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            getdis(p, edge[i].to, x, d + edge[i].val);
}

void build(int x)
{
    static int tot = 0; id[x] = ++tot;
    dfs(vn[x], x, 0, 0);
    vp[x].push_back(make_pair(-1, 0));
    vn[x].push_back(make_pair(-1, 0));
    sort(vp[x].begin(), vp[x].end());
    sort(vn[x].begin(), vn[x].end());
    for (int i = 1; i < (int)vp[x].size(); ++i)
        vp[x][i].second += vp[x][i - 1].second;
    for (int i = 1; i < (int)vn[x].size(); ++i)
        vn[x][i].second += vn[x][i - 1].second;
    vis[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to])
        {
            int root = 0; getroot(root, size[edge[i].to], edge[i].to, 0);
            fa[root] = x, dfs(vp[root], edge[i].to, 0, edge[i].val);
            build(root);
        }
    dis[x].resize(size[x]);
    getdis(x, x, 0, 0);
    vis[x] = 0;
}

int getcnt(vector<pair<int, long long> > &v, int l, int r)
{
    return lower_bound(v.begin(), v.end(), make_pair(r + 1, 0ll)) -
           lower_bound(v.begin(), v.end(), make_pair(l, 0ll));
}

long long getsum(vector<pair<int, long long> > &v, int l, int r)
{
    return (lower_bound(v.begin(), v.end(), make_pair(r + 1, 0ll)) - 1)->second -
           (lower_bound(v.begin(), v.end(), make_pair(l, 0ll)) - 1)->second;
}

long long query(int x, int l, int r)
{
    long long re = getsum(vn[x], l, r);
    int last = getcnt(vn[x], l, r), now;
    for (int i = x; fa[i]; i = fa[i])
    {
        re += dis[fa[i]][id[x] - id[fa[i]]] *
                ((now = getcnt(vn[fa[i]], l, r)) - last);
        re += getsum(vn[fa[i]], l, r) - getsum(vp[i], l, r);
        last = now;
    }
    return re;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> q >> a;
    for (int i = 1; i <= n; ++i)
        age[i] = read();
    for (int x, y, z, i = 1; i < n; ++i)
        x = read(), y = read(), z = read(),
        add(x, y, z), add(y, x, z);
    maxs[0] = 0x3f3f3f3f;
    int root = 0; getroot(root, n, 1, 0);
    build(root);
    long long ans = 0;
    for (int u, l, r, i = 1; i <= q; ++i)
    {
        u = read(), l = (read() + ans) % a, r = (read() + ans) % a;
        if (l > r) swap(l, r);
        printf("%lld\n", ans = query(u, l, r));
    }
    return 0;
}

BZOJ3924 [Zjoi2015]幻想乡战略游戏

重要的性质:∑(Dv*dist(u,v)) 是单调的,即离最终的答案点越近,得到的答案越小,于是我们只需要从分治的根往下找并递归就好了。

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

#define N 100005

int n, q, head[N], size[N], maxs[N], vis[N], id[N], fa[N], cnt[N];
long long ns[N], ps[N];
vector<long long> dis[N];
vector<pair<int, int> > son[N];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 2];

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

void dfs(int x, int fa)
{
    size[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            dfs(edge[i].to, x),
            size[x] += size[edge[i].to];
}

void getroot(int &root, int sum, int x, int fa)
{
    size[x] = 1; maxs[x] = 0;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            getroot(root, sum, edge[i].to, x),
            size[x] += size[edge[i].to],
            maxs[x] = max(maxs[x], size[edge[i].to]);
    maxs[x] = max(maxs[x], sum - size[x]);
    if (maxs[x] <= maxs[root]) root = x;
}

void getdis(int p, int x, int fa, long long d)
{
    dis[p][id[x] - id[p]] = d;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to] && edge[i].to != fa)
            getdis(p, edge[i].to, x, d + edge[i].val);
}

void build(int x)
{
    static int tot = 0;
    id[x] = ++tot, dfs(x, 0), vis[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (!vis[edge[i].to])
        {
            int root = 0; getroot(root, size[edge[i].to], edge[i].to, 0);
            son[x].push_back(make_pair(edge[i].to, root));
            fa[root] = x, build(root);
        }
    dis[x].resize(size[x]);
    getdis(x, x, 0, 0), vis[x] = 0;
}

void modify(int x, int y)
{
    for (int i = x; i; i = fa[i])
    {
        cnt[i] += y, ns[i] += dis[i][id[x] - id[i]] * y;
        if (fa[i]) ps[i] += dis[fa[i]][id[x] - id[fa[i]]] * y;
    }
}

long long query(int x)
{
    long long re = ns[x];
    for (int i = x; fa[i]; i = fa[i])
    {
        re += dis[fa[i]][id[x] - id[fa[i]]] * (cnt[fa[i]] - cnt[i]);
        re += ns[fa[i]] - ps[i];
    }
    return re;
}

long long getans(int x)
{
    long long t = query(x);
    for (int i = 0; i < (int)son[x].size(); ++i)
        if (query(son[x][i].first) < t) return getans(son[x][i].second);
    return t;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> q;
    for (int x, y, z, i = 1; i < n; ++i)
        x = read(), y = read(), z = read(),
        add(x, y, z), add(y, x, z);
    maxs[0] = 0x3f3f3f3f;
    int root = 0; getroot(root, n, 1, 0);
    build(root);
    for (int x, y, i = 1; i <= q; ++i)
    {
        x = read(), y = read();
        modify(x, y);
        printf("%lld\n", getans(root));
    }
    return 0;
}