【wc2013|wc2013 糖果公园】传送门：http://uoj.ac/problem/58
思路：果断树上莫队模板，果断看的题解，，关于时间作为第三维推来推去idea还是极好的，弄了好久就因为不明白出战入站序的性质，，，反省，而且被vfk讲晕了，，明显他的集合标准差是另一种直接在树上做的写法，还是出战入站序好用，，，本来狂WA不止，，原来是没开LL，改了还是WA，，睡了，，第二天微机课，，改了快的大小，，仍然WA，不得已看了标程，，然而，，，就把一个内容改写成了函数，，就A了，，，什么玩意，，我明明没动程序好吧，，，就是不明白啊，，，貌似还有块状树的做法，有些部分分的做法也是值得借鉴的，，，
未完待续（非常重要）
代码：
#include
#include
#include
#include
#include
#include
#define N 100000
using namespace std;
typedef long long LL;
struct edge{ int nxt,point,v;
};
struct node { int t,x,y,id;
LL ans;
};
struct data{ int num,last,now;
};
edge e[(N<<1)+5];
node que1[(N<<1)+5];
data que2[(N<<1)+5];
int n,m,q,cnt,cnt1,cnt2,time1;
int v[N+5],w[N+5],a[N+5],b[N+5],dfn[(N<<1)+5],l[N+5],r[N+5],fa[N+5][25],deep[N+5],pos[(N<<1)+5],ts[N+5];
bool vis[N+5];
LL sum;
inline void addedge(int u1,int v1){
e[++cnt].nxt = e[u1].point;
e[u1].point = cnt;
e[cnt].v = v1;
}
inline void insert(int u1,int v1){ addedge(u1,v1);
addedge(v1,u1);
}
inline bool cmp(node a,node b){
return ((pos[a.x] < pos[b.x])||(pos[a.x] == pos[b.x]&&pos[a.y]inline bool cmp1(node a,node b){ return (a.id < b.id);
}
inline int getnum(){
char c;
int num;
while (!isdigit(c = getchar()));
num = c - '0';
while (isdigit(c = getchar())) num = 10 * num + c - '0';
return num;
}void init(){
n = getnum();
m = getnum();
q = getnum();
cnt = 0;
for (int i = 1;
i <= m;
++i) v[i] = getnum();
for (int i = 1;
i <= n;
++i) w[i] = getnum();
for (int i = 1;
i < n;
++i){
int u1 = getnum(),v1 = getnum();
insert(u1,v1);
}
for (int i = 1;
i <= n;
++i) a[i] = b[i] = getnum();
time1 = 0;
}inline void dfs(int x){
l[x] = ++time1;
dfn[time1] = x;
for (int i = 1;
i <= 20;
++i) fa[x][i] = fa[fa[x][i-1]][i-1];
for (int p = e[x].point;
p;
p = e[p].nxt)
if (!l[e[p].v]) {
deep[e[p].v] = deep[x] + 1;
fa[e[p].v][0] = x;
dfs(e[p].v);
}
r[x] = ++time1;
dfn[time1] = x;
}inline int LCA(int u,int v){
if (deep[u] < deep[v]) swap(u,v);
int ll = deep[u] - deep[v];
for (int i = 20;
i >= 0;
--i)
if (ll&(1<=0;
--i)
if (fa[u][i] != fa[v][i]) u = fa[u][i],v = fa[v][i];
if (u != v) return fa[u][0];
return u;
}void sort_it(){
int sz = (int)pow(time1, 2.0 / 3.0);
for (int i = 1;
i <= time1;
++i) pos[i] = i/sz;
bool p;
int u1,v1;
cnt1 = cnt2 = 0;
for (int i = 1;
i <= q;
++i){
p = getnum();
u1 = getnum();
v1 = getnum();
if (!p) que2[++cnt2].num = u1,que2[cnt2].last = b[u1],que2[cnt2].now = b[u1] = v1;
else{ int lca = LCA(u1,v1);
if (l[u1] > l[v1]) swap(u1,v1);
que1[++cnt1].t = cnt2;
que1[cnt1].id = cnt1;
if (lca != u1) que1[cnt1].x = r[u1], que1[cnt1].y = l[v1];
else que1[cnt1].x = l[u1],que1[cnt1].y = l[v1];
}
}
sort(que1 + 1,que1 + cnt1 + 1,cmp);
//for (int i = 1;
i <= cnt1;
++i) cout< que1[i].t;
--j) modify(que2[j].num,que2[j].last);
} void make_it(){
memset(vis,0,sizeof(vis));
memset(ts,0,sizeof(ts));
//for (int i = 1;
i <= n;
++i) ts[a[i]] ++;
que1[0].t = 0;
que1[0].x = 1;
que1[0].y = 0;
sum = 0;
for (int i = 1;
i <= cnt1;
++i){
change_time(i);
//cout= que1[i].x;
--j) change(dfn[j]);
//for (int j = 1;
j <= n;
++j) cout< que1[i].y;
--j) change(dfn[j]);
//for (int j = 1;
j <= n;
++j) cout< 
