<div class="post_brief"><p>
bc的题。今天bc又挂了。这题没有写完，然后b题fst了。伤心啊。</p>

 

其实思路比较简单。直接链剖dfs序上把所有区间找出来swap就好了。不过代码实现起来还是比较麻烦的，很容易绕晕。加上smt久了没写手生了，于是就调了一晚上。唉，我还是太年轻了。

 

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;


struct node {
int v, s, sz, w, rv;
node ls, rs;
inline void update() {
sz = 1;
s = v;
if (ls) {
sz += ls-> sz;
s += ls-> s;
}
if (rs) {
sz += rs-> sz;
s += rs-> s;
}
}
inline void fix() {
if (rv) {
swap(ls, rs);
if (ls)
ls-> rv ^= 1;
if (rs)
rs-> rv ^= 1;
rv = 0;
}
}
};
typedef pair <node, node> npr;


const int maxn = 80009;


#define szof(p) ((p)?(p->sz):0)
#define sof(p) ((p)?(p->s):0)
node nlst[maxn << 1], np(nlst);
node newNode(int v) {
np-> ls = np-> rs = 0;
np-> v = np-> s = v;
np-> sz = 1;
np-> rv = 0;
#ifdef WIN32
np-> w = (rand() << 16) | rand();
#else
np-> w = rand();
#endif
return np ++;
}
node* merge(node* p, node* q) {
if (p)
p-> fix();
else
return q;
if (q)
q-> fix();
else
return p;
if (p-> w > q-> w) {
p-> rs = merge(p-> rs, q);
p-> update();
return p;
}
else {
q-> ls = merge(p, q-> ls);
q-> update();
return q;
}
}
npr split(node* p, int k) {
if (!k)
return npr(0, p);
else if (!p || p-> sz == k)
return npr(p, 0);
else {
p-> fix();
if (k <= szof(p-> ls)) {
npr g(split(p-> ls, k));
p-> ls = g. second;
p-> update();
return npr(g. first, p);
}
else {
npr g(split(p-> rs, k - szof(p-> ls) - 1));
p-> rs = g. first;
p-> update();
return npr(p, g. second);
}
}
}
int smtQry(node* p, int k) {
int s(0);
while (p && k) {
p-> fix();
if (k <= szof(p-> ls))
p = p-> ls;
else
s += sof(p-> ls) + p-> v, k -= szof(p-> ls) + 1, p = p-> rs;
}
return s;
}


struct edge {
int t;
edge *next;
};
edge *head[maxn], elst[maxn << 1], *ep(elst);
inline void addEdge(int u, int v) {
ep-> t = v;
ep-> next = head[u];
head[u] = ep ++;
}


int v[maxn], n, m;
int tc, fa[maxn], d[maxn], sz[maxn], fs[maxn], fc[maxn], ch[maxn];
int dfb[maxn], dfo[maxn];
node *rt, *remp;


void divide() {
static int stc[maxn];
int tst(1), dfn(0);
memset(fa, 0, sizeof(fa));
stc[tst] = 1;
while (tst) {
int p(stc[tst –]);
dfo[++ dfn] = p;
for (edge* e = head[p]; e; e = e-> next)
if (e-> t ^ fa[p]) {
fa[e-> t] = p;
d[e-> t] = d[p] + 1;
stc[++ tst] = e-> t;
}
}
tc = 0;
for (int i = n; i; – i) {
int p(dfo[i]);
fs[p] = -1;
sz[p] = 1;
for (edge* e = head[p]; e; e = e-> next)
if (fa[e-> t] == p) {
sz[p] += sz[e-> t];
if (fs[p] == -1 || sz[e-> t] > sz[fs[p]])
fs[p] = e-> t;
}
if (fs[p] == -1)
fc[p] = ++ tc;
else
fc[p] = fc[fs[p]];
ch[fc[p]] = p;
}
stc[tst = 1] = 1;
dfn = 0;
while (tst) {
int p(stc[tst –]);
dfo[++ dfn] = p;
dfb[p] = dfn;
for (edge* e = head[p]; e; e = e-> next)
if (fa[e-> t] == p && e-> t != fs[p])
stc[++ tst] = e-> t;
if (fs[p] != -1)
stc[++ tst] = fs[p];
}
rt = 0;
for (int i = 1; i <= n; ++ i)
rt = merge(rt, newNode(v[dfo[i]]));
remp = 0;
for (int i = 1; i <= n; ++ i)
remp = merge(remp, newNode(-1));
}


int query(int u, int v) {
int s(0);
while (fc[u] ^ fc[v])
if (d[ch[fc[u]]] > d[ch[fc[v]]]) {
s += smtQry(rt, dfb[u]) - smtQry(rt, dfb[ch[fc[u]]] - 1);
u = fa[ch[fc[u]]];
}
else {
s += smtQry(rt, dfb[v]) - smtQry(rt, dfb[ch[fc[v]]] - 1);
v = fa[ch[fc[v]]];
}
if (d[u] < d[v])
s += smtQry(rt, dfb[v]) - smtQry(rt, dfb[u] - 1);
else
s += smtQry(rt, dfb[u]) - smtQry(rt, dfb[v] - 1);
return s;
}


bool checkTree(node* p, char e) {
if (p) {
if (p-> rv) {
checkTree(p-> rs, 32);
printf("%d%c", p-> v, e);
checkTree(p-> ls, 32);
}
else {
checkTree(p-> ls, 32);
printf("%d%c", p-> v, e);
checkTree(p-> rs, 32);
}
}
return 0;
}


typedef pair <int, int> rpr;
rpr ra[maxn], rb[maxn];
void flip(int u, int v) {
int tra(0), trb(0);
while (fc[u] ^ fc[v]) {
if (d[ch[fc[u]]] > d[ch[fc[v]]]) {
ra[tra ++] = rpr(dfb[ch[fc[u]]], dfb[u]);
u = fa[ch[fc[u]]];
}
else {
rb[trb ++] = rpr(dfb[ch[fc[v]]], dfb[v]);
v = fa[ch[fc[v]]];
}
}
if (d[u] < d[v])
rb[trb ++] = rpr(dfb[u], dfb[v]);
else
ra[tra ++] = rpr(dfb[v], dfb[u]);
node *cr(0);
for (int i = 0; i < tra; ++ i) {
npr x = split(rt, ra[i]. first - 1);
npr y = split(x. second, ra[i]. second - ra[i]. first + 1);
cr = merge(y. first, cr);
npr z = split(remp, ra[i]. second - ra[i]. first + 1);
remp = z. second;
x. second = merge(z. first, y. second);
rt = merge(x. first, x. second);
}
if (cr)
cr-> rv ^= 1;
for (int i = trb - 1; i >= 0; – i) {
npr x = split(rt, rb[i]. first - 1);
npr y = split(x. second, rb[i]. second - rb[i]. first + 1);
cr = merge(cr, y. first);
npr z = split(remp, rb[i]. second - rb[i]. first + 1);
remp = z. second;
x. second = merge(z. first, y. second);
rt = merge(x. first, x. second);
}
if (cr)
cr-> rv ^= 1;
for (int i = 0; i < tra; ++ i) {
npr x = split(rt, ra[i]. first - 1);
npr y = split(x. second, ra[i]. second - ra[i]. first + 1);
npr z = split(cr, ra[i]. second - ra[i]. first + 1);
cr = z. second;
if (z. first)
z. first-> rv ^= 1;
x. second = merge(z. first, y. second);
rt = merge(x. first, x. second);
remp = merge(remp, y. first);
}
if (cr)
cr-> rv ^= 1;
for (int i = 0; i < trb; ++ i) {
npr x = split(rt, rb[i]. first - 1);
npr y = split(x. second, rb[i]. second - rb[i]. first + 1);
npr z = split(cr, rb[i]. second - rb[i]. first + 1);
cr = z. second;
if (z. first)
z. first-> rv ^= 1;
x. second = merge(z. first, y. second);
rt = merge(x. first, x. second);
remp = merge(remp, y. first);
}
}


int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif


memset(head, 0, sizeof(head));
scanf("%d%d", &amp;n, &amp;m);
for (int i = 1; i &lt;= n; ++ i)
	scanf("%d", v + i);
for (int i = 1; i &lt; n; ++ i) {
	int u, v;
	scanf("%d%d", &amp;u, &amp;v);
	addEdge(u, v);
	addEdge(v, u);
}
divide();
while (m --) {
	int opt, u, v;
	scanf("%d%d%d", &amp;opt, &amp;u, &amp;v);
	if (opt == 0)
		printf("%d\n", query(u, v));
	else
		flip(u, v);
}



}