树上莫队 TLE 求调
查看原帖
树上莫队 TLE 求调
461426
CmsMartin楼主2023/6/26 15:50
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
typedef long long ll;

namespace io {
    const int SIZE = (1 << 21) + 1;
    char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
    // getchar
    #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
    // print the remaining part
    inline void flush () {
        fwrite (obuf, 1, oS - obuf, stdout);
        oS = obuf;
    }
    // putchar
    inline void putc (char x) {
        *oS ++ = x;
        if (oS == oT) flush ();
    }
    // input a signed integer
    template <class I>
    inline void read (I &x) {
        for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
        for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
    }
    // print a signed integer
    template <class I>
    inline void print (I x) {
        if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
        while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
        while (qr) putc (qu[qr --]);
    }
    struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: putc;
using io :: print;
using io :: read;

ll N, Q, a[MAXN], Val[MAXN];

vector<int> G[MAXN];

int F[MAXN][20], Depth[MAXN];

void BFS() {
	queue<int> q;
	q.push(1);
	Depth[1] = 1;
	while(q.size()) {
		auto x = q.front();
		q.pop();
		for(auto i : G[x]) {
			if(Depth[i]) continue;
			Depth[i] = Depth[x] + 1;
			q.push(i);
			F[i][0] = x;
			for(int j = 1; j <= 18; j++) {
				F[i][j] = F[F[i][j - 1]][j - 1];
			}
		}
	}
}

int dfn[MAXN << 1], L[MAXN], R[MAXN];

void DFS(int u, int fa) {
	static int index = 0;
	Val[u] = a[u] * a[u] + Val[fa];
	dfn[++index] = u;
	L[u] = index;
	for (auto v : G[u]) {
		if (v == fa) continue;
		DFS(v, u);
	}
	dfn[++index] = u;
	R[u] = index;
}

bool Vis[MAXN];

int LCA(int x , int y) {
	if(Depth[x] < Depth[y]) swap(x , y);
	for(int i = 18; i >= 0; i--) {
		if(Depth[F[x][i]] >= Depth[y]) {
			x = F[x][i];
		}
	}
	if(x == y) return x;
	for(int i = 18; i >= 0; i--) {
		if(F[x][i] != F[y][i]) {
			x = F[x][i];
			y = F[y][i];
		}
	}
	return F[x][0];
}

struct _ {
	int x, y, id;
} Ask[MAXN];
ll Ans[MAXN];

int bel[MAXN << 1], block_size;
ll qh, sum[MAXN];

void WQH(int x) {
//	cout << x << " " << qh << " " << sum[Depth[x]] << " " << a[dfn[x]] << endl;
//	cout << endl;
	x = dfn[x];
	if (!Vis[x]) {
		qh += a[x] * sum[Depth[x]];
		sum[Depth[x]] += a[x];
	} else {
		sum[Depth[x]] -= a[x];
		qh -= a[x] * sum[Depth[x]];
	}
	Vis[x] ^= 1;
}

int main() {
	freopen("a.in", "r", stdin); 
	freopen("a.out", "w", stdout); 
	read(N); read(Q);
	for (int i = 1; i <= N; i++) read(a[i]);
	for (int i = 2; i <= N; i++) {
		static int f;
		read(f);
		G[i].push_back(f);
		G[f].push_back(i);
	}
	BFS();
	DFS(1, 0);
	for (int i = 1, x, y; i <= Q; i++) {
		read(x); read(y);
		Ans[i] = Val[LCA(x, y)];
		if (R[x] < L[y]) {
			Ask[i].x = R[x];
			Ask[i].y = L[y];
		} else {
			Ask[i].x = R[y];
			Ask[i].y = L[x];
		}
		Ask[i].id = i;
	}
	block_size = N * 2 / (sqrt(Q) + 1);
	for (int i = 1; i <= 2 * N; i++) bel[i] = (i - 1) / block_size + 1;
	sort(Ask + 1, Ask + 1 + Q, [](_ a, _ b) {
		return bel[a.x] == bel[b.x] ? (bel[a.x] & 1 ? bel[a.y] < bel[a.y] : bel[a.y] > bel[a.y]) : bel[a.x] < bel[a.x];  
	});
	for (int i = 1, l = 1, r = 0; i <= Q; i++) {
		while (r < Ask[i].y) WQH(++r);
		while (l > Ask[i].x) WQH(--l);
		while (r > Ask[i].y) WQH(r--);
		while (l < Ask[i].x) WQH(l++);
		Ans[Ask[i].id] += qh;
	}
	for (int i = 1; i <= Q; i++) {
		print(Ans[i]);
		putc('\n');
	}
	return 0;
} 
2023/6/26 15:50
加载中...