求调代码:

本地测评和洛谷ide测评输出结果不一样

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;

list<int> e[N];
int n, m, T, idx, qcnt, ccnt;
int v[N], w[N], c[N], in[N], out[N], id[N], dep[N], pos[N], dct[N], cnt[N];
bool vis[N];
ll cur, ans[N];
//id:eluar序 in, out:入出
int fa[N][22];

struct node{
	int l, r, t, id;
	bool operator<(const node &f) const{
		if (pos[l] != pos[f.l])
			return pos[l] < pos[f.l];
		if (pos[r] != pos[f.l])
			return pos[r] < pos[f.r];
		return t <= f.t;
	}
}q[N];
struct nodes{
	int x, c, t;
}Q[N];

void dfs(int u){
	id[in[u] = ++ idx] = u;
	for (int v : e[u]){
		if (v == fa[u][0]) continue;
		fa[v][0] = u, dep[v] = dep[u] + 1;
		dfs(v);
	}
	id[out[u] = ++ idx] = u;
}

int lca(int x, int y){
	if (dep[x] < dep[y]) swap(x, y);
	while (dep[x] != dep[y]){
		int dis = dep[x] - dep[y];
		for (int i = 20; i >= 0; i --){
			if (dis >= (1 << i))
				dis -= (1 << i), x = fa[x][i];
		}
	}
	if (x == y) return x;
	for (int i = 20; i >= 0; i --){
    if (fa[x][i] != fa[y][i]) 
		x = fa[x][i], y = fa[y][i];
  }
  return fa[x][0];
}

void add(int x){
  if (vis[x]) cur -= 1ll * v[c[x]] * w[cnt[c[x]] --];
  else cur += 1ll * v[c[x]] * w[++ cnt[c[x]]];
  vis[x] ^= 1;
}

void modify(int x, int y){
  if (vis[x]) add(x), c[x] = y, add(x);
  else c[x] = y;
}

void solve(){
	// read(n), read(m), read(T);
	cin >> n >> m >> T;
	for (int i = 1; i <= m; i ++) cin >> v[i];//read(v[i]);
	for (int i = 1; i <= n; i ++) cin >> w[i];//read(w[i]);
	for (int i = 1, u, v; i < n; i ++){
		// read(u), read(v);
		cin >> u >> v;
		e[u].push_back(v), e[v].push_back(u);
	}
	for (int i = 1; i <= n; i ++) cin >> dct[i], c[i] = dct[i];
	dfs(1);
	for (int j = 1; j <= 20; j ++)
		for (int i = 1; i <= n; i ++)
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
	int Bs = pow(idx, 2. / 3);
	for (int i = 1; i <= idx; i ++)
		pos[i] = (i - 1) / Bs;
	for (int i = 1, op, x, y; i <= T; i ++){
		// read(op), read(x), read(y);
		cin >> op >> x >> y;
		if (op == 0) ++ ccnt, Q[ccnt] = (nodes){x, dct[x], y}, dct[x] = y;
		else{
			if (in[x] > in[y]) swap(x, y);
			++ qcnt, q[qcnt] = (node){lca(x, y) == x ? in[x] : out[x], in[y], ccnt, qcnt};
		}
	}
	sort(q + 1, q + 1 + qcnt);
  // return;
	int L = 0, R = 0, t = 1;
	for (int i = 1; i <= qcnt; i ++){
		while (t <= q[i].t) modify(Q[t].x, Q[t ++].t);
		while (t > q[i].t) modify(Q[t].x, Q[t --].c);
		while (L > q[i].l) add(id[-- L]);
		while (L < q[i].l) add(id[L ++]);
		while (R > q[i].r) add(id[R --]);
		while (R < q[i].r) add(id[++ R]);
    int x = id[L], y = id[R];
    int LCA = lca(x, y);
    if (x != LCA && y != LCA){
      add(LCA);
      ans[q[i].id] = cur;
      add(LCA);
    }
    else
      ans[q[i].id] = cur;
      // cout << q[i].id << ":" << cur << '\n';
	}
  for (int i = 1; i <= qcnt; i ++)
    cout << ans[i] << '\n';
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	// read(T);
	// while (T --)
		solve();
	return 0;
}