啊啊看到动态树被吓尿了。


然后发现动的不是树的形态是点权。


树链剖分+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);

}

}

}