D2T3 centroid

Solution

考虑每个点 (u) 作为重心的贡献
假设以 (u) 为根时，存在 (u) 的一个子节点 (v)
现在要在 (v) 的子树内删掉一个子树，使得 (u) 成为重心
考虑删子树之后，(v) 的子树大小需要满足什么条件
设 (u) 除 (v) 之外，所有子树大小的和为 (s) ，最大子树大小为 (m)
（1）(v) 的子树大小不能比 (u) 其他子树大小的和加 (1) 还大：
[size_vle s+1 ]
（2）除 (v) 之外的最大子树大小不能比 (u) 其他子树大小的和加 (1) 还大：
[mle s-m+size_v+1 ]
于是得出 (size_vin[2m-s-1,s+1])
问题转化为 (v) 的子树内有多少个点的子树大小在某个区间范围内
由于我们不能每次都以 (u) 为根重新求一遍，所以任选一个点为根后，如果 (v) 是 (u) 的子节点，那么可以直接利用各种方法（如线段树合并）统计，否则分删掉的子树是否在 (1) 到 (u) 的路径上进行处理
(O(nlog n))

Code

#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
	res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	if (bo) res = ~res + 1;
}

template <class T>
inline void Swap(T &a, T &b) {T t = a; a = b; b = t;}

typedef long long ll;

const int N = 3e5 + 5, M = N << 1, L = 1e7 + 5;

int n, ecnt, nxt[M], adj[N], go[M], sze[N], rt[N], ToT, A[N], sum[N];
ll ans;

struct node
{
	int lc, rc, sum;
} T[L];

void change(int x, int v)
{
	for (; x <= n; x += x & -x)
		A[x] += v;
}

int ask(int x)
{
	int res = 0;
	for (; x; x -= x & -x)
		res += A[x];
	return res;
}

void ins(int l, int r, int pos, int v, int &p)
{
	if (!p) p = ++ToT;
	T[p].sum += v;
	if (l == r) return;
	int mid = l + r >> 1;
	if (pos <= mid) ins(l, mid, pos, v, T[p].lc);
	else ins(mid + 1, r, pos, v, T[p].rc);
}

int query(int l, int r, int s, int e, int p)
{
	if (!p || e < l || s > r) return 0;
	if (s <= l && r <= e) return T[p].sum;
	int mid = l + r >> 1;
	return query(l, mid, s, e, T[p].lc) + query(mid + 1, r, s, e, T[p].rc);
}

int mer(int x, int y)
{
	if (!x || !y) return x ^ y;
	T[x].sum += T[y].sum;
	T[x].lc = mer(T[x].lc, T[y].lc);
	T[x].rc = mer(T[x].rc, T[y].rc);
	return x;
}

void add_edge(int u, int v)
{
	nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
	nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;
}

void dfs(int u, int fu)
{
	sze[u] = 1;
	for (int e = adj[u], v; e; e = nxt[e])
		if ((v = go[e]) != fu) dfs(v, u), sze[u] += sze[v];
}

void solve(int u, int fu)
{
	int pm = 0, pc = 0;
	for (int e = adj[u], v; e; e = nxt[e])
	{
		if ((v = go[e]) == fu) continue;
		if (sze[v] > pm) pc = pm, pm = sze[v];
		else if (sze[v] > pc) pc = sze[v];
	}
	if (fu)
	{
		if (n - sze[u] > pm) pc = pm, pm = n - sze[u];
		else if (n - sze[u] > pc) pc = n - sze[u];
	}
	for (int e = adj[u], v; e; e = nxt[e])
	{
		if ((v = go[e]) == fu) continue;
		change(sze[v], 1); solve(v, u); change(sze[v], -1);
		int mx = sze[v] == pm ? pc : pm;
		int l = n - sze[v], r = mx - (l - mx);
		l = sze[v] - l; r = sze[v] - r;
		if (l > r || r < 1 || l > n) {rt[u] = mer(rt[u], rt[v]); continue;}
		if (l < 1) l = 1; if (r > n) r = n;
		ans += 1ll * u * query(1, n, l, r, rt[v]);
		rt[u] = mer(rt[u], rt[v]);
	}
	if (u == 1) return;
	int mx = n - sze[u] == pm ? pc : pm;
	int l = sze[u], r = mx - (l - mx);
	l = n - sze[u] - l; r = n - sze[u] - r;
	if (l > r || r < 1 || l > n) return ins(1, n, sze[u], 1, rt[u]);
	if (l < 1) l = 1; if (r > n) r = n;
	int cnt = sum[r] - sum[l - 1] - query(1, n, l, r, rt[u]);
	cnt -= ask(r) - ask(l - 1);
	l = n - l; r = n - r; Swap(l, r);
	if (l > r || r < 1 || l > n) return ins(1, n, sze[u], 1, rt[u]);
	if (l < 1) l = 1; if (r > n) r = n;
	cnt += ask(r) - ask(l - 1); ans += 1ll * u * cnt;
	ins(1, n, sze[u], 1, rt[u]);
}

void work()
{
	int x, y;
	read(n);
	ecnt = ToT = 0; ans = 0;
	memset(adj, 0, sizeof(adj));
	memset(rt, 0, sizeof(rt));
	memset(A, 0, sizeof(A));
	memset(sum, 0, sizeof(sum));
	for (int i = 1; i < n; i++) read(x), read(y), add_edge(x, y);
	dfs(1, 0);
	for (int i = 2; i <= n; i++) sum[sze[i]]++;
	for (int i = 1; i <= n; i++) sum[i] += sum[i - 1];
	solve(1, 0);
	printf("%lld
", ans);
	for (int i = 1; i <= ToT; i++) T[i].lc = T[i].rc = T[i].sum = 0;
}

int main()
{
	int T; read(T);
	while (T--) work();
	return 0;
}

D2T2 partition

Solution

我们大胆猜想：当答案取到最优时，最后一段的长度取到最小值
证明略 ~~（显然）~~
设 (f_i) 表示以 (i) 为结尾，倒数第二段结束位置的最大值，如果最优答案下只有一段则为 (0)
设 (sum) 为前缀和数组
那么我们有
[f_i=max{j|sum_i-sum_jge sum_j-sum_{f_j}} ]
也就是
[f_i=max{j|0le j<i,sum_ige2sum_j-sum_{f_j}} ]
考虑维护一个以 (2sum_j-sum_{f_j}) 为关键字的，关于后缀最小值的单调栈
那么我们每次要选取的就是单调栈中，从右到左第一个不超过 (sum_i) 的元素
由于 (sum) 单调递增，故可以用一个指针维护这个元素的位置
注意单调栈退栈的时候，如果这时指针不在栈内了，那么要把指针重新放到栈顶
最后从 (i=n) 开始，不断让 (ileftarrow f_i) ，期间把 ((sum_i-sum_{f_i})^2) 计入答案，需要使用到高精度
(O(n))

Code

#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
	res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	if (bo) res = ~res + 1;
}

typedef long long ll;

const int N = 4e7 + 5, M = 1e5 + 5, rqy = 1 << 30, dmy = 1e9;

int n, ty, f[N], X, Y, Z, m, p[M], l[M], r[M], top, stk[N];
ll sum[N], tmp[4];

struct gao
{
	int a[4];
	
	friend inline gao operator + (gao a, gao b)
	{
		gao res;
		res.a[0] = res.a[1] = res.a[2] = res.a[3] = 0;
		res.a[0] += a.a[0] + b.a[0];
		if (res.a[0] >= dmy) res.a[1]++, res.a[0] -= dmy;
		res.a[1] += a.a[1] + b.a[1];
		if (res.a[1] >= dmy) res.a[2]++, res.a[1] -= dmy;
		res.a[2] += a.a[2] + b.a[2];
		if (res.a[2] >= dmy) res.a[3]++, res.a[2] -= dmy;
		return res.a[3] += a.a[3] + b.a[3], res;
	}
} ans, tm;

gao sqr(gao x)
{
	tmp[0] = 1ll * x.a[0] * x.a[0]; tmp[1] = 2ll * x.a[0] * x.a[1];
	tmp[2] = 1ll * x.a[1] * x.a[1]; tmp[3] = 0;
	for (int i = 0; i < 3; i++)
		tmp[i + 1] += tmp[i] / dmy, tmp[i] %= dmy;
	gao res; res.a[0] = tmp[0]; res.a[1] = tmp[1];
	return res.a[2] = tmp[2], res.a[3] = tmp[3], res;
}

int main()
{
	read(n); read(ty);
	if (ty)
	{
		read(X); read(Y); read(Z); read(sum[1]); read(sum[2]); read(m);
		for (int i = 3; i <= n; i++)
			sum[i] = (sum[i - 1] * X + sum[i - 2] * Y + Z) % rqy;
		for (int i = 1; i <= m; i++)
			read(p[i]), read(l[i]), read(r[i]);
		for (int j = 1; j <= m; j++)
			for (int i = p[j - 1] + 1; i <= p[j]; i++)
				sum[i] %= r[j] - l[j] + 1, sum[i] += l[j];
	}
	else for (int i = 1; i <= n; i++) read(sum[i]);
	for (int i = 1; i <= n; i++) sum[i] += sum[i - 1];
	stk[top = 1] = 0; int p = 1;
	for (int i = 1; i <= n; i++)
	{
		while (p < top && sum[stk[p + 1]] * 2 - sum[f[stk[p + 1]]] <= sum[i]) p++;
		f[i] = stk[p];
		while (top && sum[stk[top]] * 2 - sum[f[stk[top]]]
			>= sum[i] * 2 - sum[f[i]]) top--;
		if (p > top) p = top; stk[++top] = i;
	}
	for (int i = n; i; i = f[i])
	{
		ll num = sum[i] - sum[f[i]];
		tm.a[0] = num % dmy; tm.a[1] = num / dmy;
		ans = ans + sqr(tm);
	}
	bool is = 0;
	for (int i = 3; i >= 0; i--)
	{
		if (!ans.a[i] && !is) continue;
		if (!is) printf("%d", ans.a[i]), is = 1;
		else printf("%09d", ans.a[i]);
	}
	if (is) puts(""); else puts("0");
	return 0;
}

D1T3 tree

Solution

先按字典序从左到右贪心，设数 (i) 在点 (u)
现在要为 (u) 选定一个编号最小的点 (v) （(u e v)），且需要满足一些条件
设前 (i-1) 个数已经定好了位置，我们现在要判定的就是如果想要把数 (i) 移到点 (v) ，那么是否存在一个操作次序
这时从 (u) 到 (v) 连一条路径，可以得出：
（1）路径上第一条边比 (u) 出发的任意其他边的操作次序都早
（2）路径上最后一条边比 (v) 出发的任意其他边的操作次序都晚
（3）对于路径上任意相邻的两条边 (e_1,e_2) ，如果它们有公共点 (x) ，那么就 (x) 出发的所有边中，(e_1) 和 (e_2) 的操作次序必须相邻，并且 (e_1) 先于 (e_2)
不难发现产生的所有限制关系都在有公共点的两条边之间产生
同时，由于这是一棵树，所以如果对于任意 (u) 都满足 (u) 出发的任意边之间都不会产生矛盾，那么整棵树都不会产生矛盾（因为可以不断删叶子）
由于我们有两条边操作次序相邻的限制，故可以对每个点，用并查集或链表维护连续段，对 (i) 确定位置 (v) 时判断是否合法
如何判断合法性：
（1）设 (u) 到 (v) 的路径上第一条边为 (e) ，那么需要满足 (e) 是某个连续段的开头，并且 (u) 出发的所有边已经被合成一个连续段，或者 (e) 所在连续段的末尾没有被钦定为最后一次操作
（2）最后一条边同理
（3）对于路径上连续的两条边 (e_1,e_2) ，需要满足：
① (e_1) 是某个连续段的末尾，(e_2) 是某个连续段的开头，且 (e_1) 和 (e_2) 不属于同一连续段
② (e_1) 没有被钦定为最后一次操作，并且 (e_2) 没有被钦定为第一次操作
③ 如果 (e_1) 所在连续段的开头被钦定为第一次操作，且 (e_2) 所在连续段的末尾被钦定为最后一次操作，那么需要满足以 (u) 出发的边中，除了 (e_1) 和 (e_2) 各自所在的连续段之外，不能有其他的连续段
找到了对应的 (v) 时，需要把 (u) 到 (v) 的路径上所有相邻的两条边合并连续段，并把第一条边钦定为第一次操作，最后一条边钦定为最后一次操作
(O(Tn^2))

Code

#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
	res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	if (bo) res = ~res + 1;
}

const int N = 2005, M = N << 1;

int n, a[N], ecnt, nxt[M], adj[N], go[M], res, d[N],
st[M], ed[M], fir[M], lst[M], par[N];
bool ist[M], ied[M], vis[N];

void add_edge(int u, int v)
{
	nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
	nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;
	d[u]++; d[v]++;
}

void dfs(int u, int fu, int fe)
{
	if (ied[fe] && (d[u] == 1 || st[fe] != fir[u]) && u < res && !vis[u]) res = u;
	for (int e = adj[u], v; e; e = nxt[e])
	{
		if ((v = go[e]) == fu) continue;
		if (!ied[fe] || !ist[e] || ed[e] == fe) continue;
		if (fir[u] == e || lst[u] == fe) continue;
		if (fir[u] == st[fe] && lst[u] == ed[e] && d[u] > 2) continue;
		dfs(v, u, par[v] = e ^ 1);
	}
}

void work()
{
	int x, y;
	read(n); ecnt = 1;
	memset(adj, 0, sizeof(adj)); memset(vis, 0, sizeof(vis));
	memset(fir, 0, sizeof(fir)); memset(lst, 0, sizeof(lst));
	memset(ist, 1, sizeof(ist)); memset(ied, 1, sizeof(ied));
	memset(d, 0, sizeof(d));
	for (int i = 1; i <= n; i++) read(a[i]);
	for (int i = 1; i < n; i++) read(x), read(y), add_edge(x, y);
	for (int i = 2; i <= ecnt; i++) st[i] = ed[i] = i;
	for (int i = 1; i <= n; i++)
	{
		int u = a[i]; res = n;
		for (int e = adj[u], v = go[e]; e; e = nxt[e], v = go[e])
			if (ist[e] && (d[u] == 1 || ed[e] != lst[u]))
				dfs(v, u, par[v] = e ^ 1);
		printf("%d ", res); vis[res] = 1;
		lst[res] = par[res]; int e = par[res] ^ 1;
		for (int v = go[par[res]]; v != u; v = go[par[v]])
		{
			int f = par[v], l = st[f], r = ed[e];
			st[r] = l; ed[l] = r; ied[f] = ist[e] = 0;
			e = f ^ 1; d[v]--;
		}
		fir[u] = e;
	}
	puts("");
}

int main()
{
	int T; read(T);
	while (T--) work();
	return 0;
}