BZOJ3589 动态树
啊啊看到动态树被吓尿了。
然后发现动的不是树的形态是点权。
树链剖分+dfs序么。
重点是我TLE了。
最初的写法是直接查询然后把访问过的点打个标记。一个询问做完再标记回去。然后，tle。
参考jason_yu的做法，找出所有dfs序上要询问的区间，合并之后询问，应该不会tle了吧？还是tle。
最后发现是线段树lazy标记的地方写成n^2了。开心啊。
事实证明第一种写法12秒左右，第二种写法3秒多。当然也要考虑我巨丑的常数。
所以我还是太naive了。
代码当然要粘快的。
#include <cstdio>
#include <cctype>
#include <memory.h>
#include <algorithm>
using namespace std;
struct edge {
int t;
edge *next;
};
struct seg {
int l, r, a, v;
seg *ls, *rs;
};
struct rect {
int l, r;
inline rect(int l0 = 0, int r0 = 0) {
l = l0, r = r0;
}
inline rect operator +(const rect& a) const {
return rect(min(l, a. l), max(r, a. r));
}
inline rect operator =(const rect& a) {
l = a. l, r = a. r;
return *this;
}
};
inline bool cmpRect(const rect& a, const rect& b) {
return a. l < b. l;
}
#define readInt(_s_) {\
int _d_;\
_s_ = 0;\
while (!isdigit(_d_ = getchar()));\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
}
const int maxn = 200009;
int n, q, dfo[maxn], dfb[maxn], dfe[maxn];
int fs[maxn], fa[maxn], d[maxn], fc[maxn], ch[maxn], sz[maxn], tc;
int tre;
rect cre[maxn];
edge *head[maxn], *ep;
seg *rt, *sp;
inline void addEdge(int u, int v) {
ep-> t = v;
ep-> next = head[u];
head[u] = ep ++;
}
#define mid(p) ((p->l+p->r)>>1)
inline seg *sgtBuild(int l, int r) {
seg* p = sp ++;
p-> l = l;
p-> r = r;
p-> a = 0;
p-> v = 0;
if (l + 1 < r) {
p-> ls = sgtBuild(l, mid(p));
p-> rs = sgtBuild(mid(p), r);
}
return p;
}
inline void sgtAdd(seg* p, int l, int r, int v) {
if (p-> l == l && p-> r == r)
p-> a += v;
else if (r <= mid(p))
sgtAdd(p-> ls, l, r, v);
else if (l >= mid(p))
sgtAdd(p-> rs, l, r, v);
else {
sgtAdd(p-> ls, l, mid(p), v);
sgtAdd(p-> rs, mid(p), r, v);
}
p-> v += v * (r - l);
}
inline int sgtQry(seg* p, int l, int r) {
if (p-> l == l && p-> r == r)
return p-> v;
else {
int a = (r - l) * p-> a;
if (r <= mid(p))
return sgtQry(p-> ls, l, r) + a;
else if (l >= mid(p))
return sgtQry(p-> rs, l, r) + a;
else
return sgtQry(p-> ls, l, mid(p)) + sgtQry(p-> rs, mid(p), r) + a;
}
}
void divide() {
static int stc[maxn];
int tstc = 1, dfn = 0;
memset(d, 0, sizeof(d));
stc[1] = 1;
d[1] = 1;
while (tstc) {
int p = stc[tstc --];
dfb[p] = ++ dfn;
dfo[dfn] = p;
for (edge* e = head[p]; e; e = e-> next)
if (!d[e-> t]) {
d[e-> t] = d[p] + 1;
fa[e-> t] = p;
stc[++ tstc] = e-> t;
}
}
tc = 0;
for (int i = n; i; -- i) {
int p = dfo[i], x = -1;
sz[p] = 1;
for (edge* e = head[p]; e; e = e-> next)
if (fa[e-> t] == p) {
sz[p] += sz[e-> t];
if (x == -1 || sz[e-> t] > sz[x])
x = e-> t;
}
fs[p] = x;
if (x > -1) {
fc[p] = fc[x];
ch[fc[p]] = p;
}
else {
fc[p] = ++ tc;
ch[fc[p]] = p;
}
}
tstc = 1;
stc[1] = 1;
dfn = 0;
while (tstc) {
int p = stc[tstc --];
dfb[p] = ++ dfn;
dfe[p] = dfb[p];
dfo[dfn] = p;
for (edge* e = head[p]; e; e = e-> next)
if (fa[e-> t] == p && e-> t != fs[p])
stc[++ tstc] = e-> t;
if (fs[p] > -1)
stc[++ tstc] = fs[p];
}
for (int i = n; i > 1; -- i)
dfe[fa[dfo[i]]] = max(dfe[fa[dfo[i]]], dfe[dfo[i]]);
rt = sgtBuild(1, n + 1);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
memset(head, 0, sizeof(head));
ep = new edge[maxn * 2];
sp = new seg[maxn * 3];
readInt(n);
for (int i = 0; i < n - 1; ++ i) {
int u, v;
readInt(u);
readInt(v);
addEdge(u, v);
addEdge(v, u);
}
divide();
readInt(q);
while (q --) {
int k, u, v;
readInt(k);
if (!k) {
readInt(u);
readInt(v);
sgtAdd(rt, dfb[u], dfe[u] + 1, v);
}
else {
readInt(k);
int ans = 0;
tre = 0;
for (int i = 0; i < k; ++ i) {
readInt(u);
readInt(v);
if (d[u] < d[v])
swap(u, v);
while (fc[u] ^ fc[v]) {
cre[tre ++] = rect(dfb[ch[fc[u]]], dfb[u] + 1);
u = fa[ch[fc[u]]];
}
cre[tre ++] = rect(dfb[v], dfb[u] + 1);
}
sort(cre, cre + tre, cmpRect);
for (int i = 0; i < tre; ++ i)
if (i < tre - 1 && cre[i]. r >= cre[i + 1]. l)
cre[i + 1] = cre[i] + cre[i + 1];
else
ans += sgtQry(rt, cre[i]. l, cre[i]. r);
printf("%d\n", ans & 2147483647);
}
}
}
