模板

开个坑写一下一些模板

树

长链剖分

#include <bits/stdc++.h>

#define pb emplace_back

using namespace std;
typedef long long LL;

const int maxn = 1e6 + 5;
const int INF = 1e9 + 7;

LL *now;
LL *F[maxn];
LL buf[maxn << 1];


int n;
vector<int> E[maxn];
int A[maxn], mi[maxn][21];
int son[maxn], dep[maxn], mx[maxn];
int lg[maxn];

template<typename T>
void read(T &x)
{
	x = 0;
	int fl = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-')
		ch = getchar();
	if(ch == '-')
		fl = -1, ch = getchar();
	while(isdigit(ch))
		x = x * 10 + ch - '0', ch = getchar();
	x *= fl;
}

void dfs1(int x, int fr)
{
	for(auto &v : E[x]){
		if(v == fr)
			continue;
		dep[v] = dep[x] + 1;
		dfs1(v, x);
		if(mx[v] > mx[son[x]])
			son[x] = v;
		mx[x] = max(mx[x], mx[v]);
	}
	mx[x] += 1;
}

int ask(int l, int r)
{
	int t = lg[r - l + 1];
	return min(mi[l][t], mi[r - (1 << t) + 1][t]);
}

void dp(int x, int fr)
{
	F[x][0] = A[0];
	if(son[x]){
		F[son[x]] = F[x] + 1;
		dp(son[x], x);
	}

	int _mx = 0;
	for(auto &v : E[x]){
		if(v == fr || v == son[x])
			continue;
		F[v] = now;
		now += mx[v];
		_mx = max(_mx, mx[v] + 1);
		dp(v, x);
		for(int j = 0; j < mx[v]; ++j){
			F[x][j + 1] += F[v][j]; 
		}
			
	}
	for(int j = 0; j <= _mx; ++j)
		F[x][j] = min(F[x][j], 1LL * ask(j, dep[x] + j));
}

int main()
{
	int T;
	read(T);
	while(T--){
		read(n);		
		for(int i = 0; i <= now - buf; ++i)
			buf[i] = 0;
		for(int i = 2; i <= n; ++i)
			lg[i] = lg[i >> 1] + 1;
		for(int i = 1; i <= n; ++i)
			E[i].clear(), son[i] = dep[i] = mx[i] = 0;
		for(int i = 0; i <= n - 1; ++i){
			read(A[i]);
			mi[i][0] = A[i];
		}

		for(int j = 1; j <= lg[n]; ++j)
			for(int i = 0; i + (1 << j) - 1 <= n - 1; ++i)
				mi[i][j] = min(mi[i][j - 1], mi[i + (1 << (j - 1))][j - 1]);

		for(int i = 1; i <= n - 1; ++i){
			int u, v;
			read(u), read(v);
			E[u].pb(v), E[v].pb(u);
		}

		dfs1(1, 0);


		now = buf;
		F[1] = now;
		now += mx[1];
		dp(1, 0);

		LL ans = 0;
		for(int i = 0; i < mx[1]; ++i)
			ans += F[1][i];
		cout << ans << endl;
	}
}