2017JLU校赛-H

发表于 |

题目

给一棵有N个节点的树，边权非负。有M个操作。

操作有2种：

  1. 指定子树中的边权都加上某个数。
  2. 输出节点x到节点y的路径上的边权的平方和。

数据范围

$ 0 \leq N, M \leq 200000 $

做法

下面的2种做法，一般都是处理点权的。对于边的边权，要将其转化为终点t的点权。

下面讲一下如何用线段树维护区间平方和。

对于区间[l, r)，其中朝向叶子的边的个数为np，朝向根的边的个数nn=r-l-np。朝向叶子的边的权值和为sp，朝向根的边的权值和为sn，整个区间的边权平方和为s2。

那么，对区间的边权都加上c，只要做如下处理：

1
2
3
4
5
s2 += np * c * c + 2 * c * sp;
s2 += -nn * c * c + 2 * c * sn;
sp += np * c;
sn -= nn * c;
add += c; // lazy标记

DFS序+线段树

在求DFS序的时候，每条边都会经过2次。经过某条边时，如果方向是朝叶子方向，那么我们就令边权为原来的边权，而如果方向是朝根的方向，我们就令边权为原来边权的相反数。

用线段树来维护DFS序上的边权。因为同一子树内的点的DFS序是连续的一段，那么操作1就是线段树的区间修改。对于操作2，由于我们给赋值边权的方法，线段树上id[lca(x, y)]到id[x]的这段区间的和加上id[lca(x, y)]到id[y]的这段区间的和就是答案，因为重复经过的边求和时正负相消。（id[x]：进入点x时DFS的时间戳）。

复杂度是$O(M \times log_2N)$。

树链剖分+线段树

由于树链剖分有这个性质：同一子树内的点在线段树上的标号也是连续的一段，所以这题也能用树链剖分来做。操作1就是区间修改，操作2就是区间求和。

复杂度是$O(M \times log_2N \times log_2N)$

代码

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
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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
#include <bits/stdc++.h>
#define lson (2 * k + 1)
#define rson (2 * k + 2)
using namespace std;
typedef long long ll;
const int MAX_V = 2e5 + 5;
struct Edge
{
  int to, cost;
};
struct ST1
{
  int *src;
  bool *toLeaf;
  int sp[(MAX_V * 2) << 2], sn[(MAX_V * 2) << 2];
  int s2[(MAX_V * 2) << 2];
  int n[(MAX_V * 2) << 2];
  int add[(MAX_V * 2) << 2];
  void updateAdd(int c, int l, int r, int k)
  {
    int n2 = r - l - n[k];
    s2[k] += n[k] * c * c + 2 * c * sp[k];
    s2[k] += -n2 * c * c + 2 * c * sn[k];
    sp[k] += n[k] * c;
    sn[k] -= n2 * c;
    add[k] += c;
  }
  void pushUp(int k)
  {
    sp[k] = sp[lson] + sp[rson];
    sn[k] = sn[lson] + sn[rson];
    s2[k] = s2[lson] + s2[rson];
    n[k] = n[lson] + n[rson];
  }
  void pushDown(int l, int r, int k)
  {
    if (add[k]) {
      updateAdd(add[k], l, (l + r) / 2, lson);
      updateAdd(add[k], (l + r) / 2, r, rson);
      add[k] = 0;
    }
  }
  void build(int l, int r, int k)
  {
    add[k] = 0;
    if (r - l == 1) {
      sp[k] = sn[k] = 0;
      if (toLeaf[l]) {
        sp[k] = src[l];
        s2[k] = src[l] * src[l];
        n[k] = 1;
      } else {
        sn[k] = -src[l];
        s2[k] = -src[l] * src[l];
        n[k] = 0;
      }
      return;
    }
    build(l, (l + r) / 2, lson);
    build((l + r) / 2, r, rson);
    pushUp(k);
  }
  void update(int a, int b, int c, int l, int r, int k)
  {
    if (b <= l || r <= a) return;
    if (a <= l && r <= b) {
      updateAdd(c, l, r, k);
      return;
    }
    pushDown(l, r, k);
    update(a, b, c, l, (l + r) / 2, lson);
    update(a, b, c, (l + r) / 2, r, rson);
    pushUp(k);
  }
  int query(int a, int b, int l, int r, int k)
  {
    if (b <= l || r <= a) return 0;
    if (a <= l && r <= b) return s2[k];
    pushDown(l, r, k);
    int vl = query(a, b, l, (l + r) / 2, lson);
    int vr = query(a, b, (l + r) / 2, r, rson);
    return vl + vr;
  }
};
struct ST2
{
  int *src;
  int dat[(MAX_V * 2) << 2];
  void pushUp(int k)
  {
    if (src[dat[lson]] < src[dat[rson]]) dat[k] = dat[lson];
    else dat[k] = dat[rson];
  }
  void build(int l, int r, int k)
  {
    if (r -l == 1) {
      dat[k] = l;
      return;
    }
    build(l, (l + r) / 2, lson);
    build((l + r) / 2, r, rson);
    pushUp(k);
  }
  int query(int a, int b, int l, int r, int k)
  {
    if (b <= l || r <= a) return -1;
    if (a <= l && r <= b) return dat[k];
    int vl = query(a, b, l, (l + r) / 2, lson);
    int vr = query(a, b, (l + r) / 2, r, rson);
    if (vl == -1 || vr == -1) {
      return max(vl, vr);
    } else {
      if (src[vl] < src[vr]) return vl;
      else return vr;
    }
  }
};
int V;
vector<Edge> G[MAX_V];
int vs[MAX_V * 2 - 1];
int dep[MAX_V* 2 - 1];
int id[MAX_V];
int id2[MAX_V];
int cost[MAX_V * 2];
bool toLeaf[MAX_V * 2];
int N1;
ST1 st1;
int N2;
ST2 st2;
void addEdge(int a, int b, int c)
{
  G[a].push_back((Edge){b, c});
  G[b].push_back((Edge){a, c});
}
void getDfn(int v, int p, int d, int &k)
{
  id[v] = k;
  id2[v] = k;
  vs[k] = v;
  dep[k++] = d;
  for (int i = 0; i < (int)G[v].size(); ++i) {
    Edge &e = G[v][i];
    if (e.to != p) {
      cost[k] = e.cost;
      toLeaf[k] = true;
      getDfn(e.to, v, d + 1, k);
      cost[k] = e.cost;
      toLeaf[k] = false;
      id2[v] = k;
      vs[k] = v;
      dep[k++] = d;
    }
  }
}
int getLca(int a, int b)
{
  return vs[st2.query(min(id[a], id[b]), max(id[a], id[b]) + 1, 0, N2, 0)];
}
void init()
{
  int k = 0;
  getDfn(0, -1, 0, k);
  N1 = 2 * (V - 1) + 1;
  st1.src = cost;
  st1.toLeaf = toLeaf;
  st1.build(1, N1, 0);
  N2 = 2 * V - 1;
  st2.src = dep;
  st2.build(0, N2, 0);
}
int main()
{
  scanf("%d", &V);
  for (int i = 1; i < V; ++i) {
    int a, b, c; scanf("%d%d%d", &a, &b, &c); --a; --b;
    addEdge(a, b, c);
  }
  init();
  int Q; scanf("%d", &Q);
  while (Q--) {
    int op, a, b; scanf("%d%d%d", &op, &a, &b);
    if (op == 1) {
      --a;
      if (id[a] != id2[a]) {
        st1.update(id[a] + 1, id2[a] + 1, b, 1, N1, 0);
      }
    } else {
      --a; --b;
      int p = getLca(a, b);
      int ans = 0;
      if (p != a) ans += st1.query(id[p] + 1, id[a] + 1, 1, N1, 0);
      if (p != b) ans += st1.query(id[p] + 1, id[b] + 1, 1, N1, 0);
      printf("%d\n", ans);
    }
  }
  return 0;
}

树链剖分+线段树

1
2

注意

  1. 最好新开一个数组标记一下这条边的朝向，而不是靠边权的正负来判断，这样适应性更强。
  2. 我的线段树递归的时候是不判断区间的合法性的，要在调用的时候就判断合法性。