[校内训练]palace(点分治+启发式合并)

摘要:
解决方案考虑了一种非常暴力的方法:注意作为路径端点的法律解决方案的数量。合法方案的总数是因为方案包含不同的终结点。这可以通过dfs获得一次。然后计算子树外部表示相同颜色的路径数,并记录此时的父节点。它只与子树中每种颜色的点数有关,可以启发式合并。对于每一项,我们可以计算对的贡献,只要我们知道满意度和。当枚举到子节点时,首先dfs子树,使用前一个(C,S)数组对子树中的点进行贡献,然后再次dfs子树以更新(C,S)数组。

Description

给定一棵 (n) 个节点的树,每个节点有一个颜色 (c_i)

要求选出两条不相交的路径 ((x,y),(u,v)),满足 (c_x=c_y)(c_u=c_v)

((x,y),(u,v))((u,v),(x,y)) 算同一种方案。

求有多少种合法方案。

还有 (m) 个询问,第 (i) 次询问 (k_i) 不能作为路径端点的方案数。

方案数全部对 (10^9+7) 取模。

记颜色种类数为 (q),则 (n,m,qle10^5)

时空限制 ( ext{1s/512MB})

Solution

考虑一种非常暴力的做法:

(ans_x) 表示 (x) 作为路径端点的合法方案数。

枚举路径 ((x,y)),满足 (c_x=c_y),接下来算出和 ((x,y)) 不相交的路径数 (cnt)

然后把 (ans_x,ans_y) 都加上 (cnt)

总合法方案数是 (frac{1}{4}sum_{i=1}^nans_i),因为一个方案包含 (4) 个互不相同的端点。

然而 (nle 10^5),显然不能直接枚举 (x,y)

考虑点分治,即设重心为 (G),算出经过点 (G) 的路径 ((x,y)) 的贡献。

(f[u]) 表示以 (G) 为根时,(u) 的子树内有多少条端点同色的路径。

那么不和 ((x,y)) 相交的同色路径数就是下图中绿色点的 (f) 之和:

在这里插入图片描述
具体地,记 (sum)(G) 所有子节点的 (f) 之和。

(g[x]) 为所有满足以下条件的点 (v)(f[v]) 之和:

  1. 存在某个点 (u),使得 (u) 是路径 ((G,x)) 上的点,且 (u)(v) 有边。
  2. (v) 不是路径 ((G,x)) 上的点。
  3. (v) 不是 (G) 的子节点。

(G) 的深度为 (1),记 (h[x]) 表示路径 ((G,x)) 上深度为 (2) 的点的 (f) 值。

那么与 ((x,y)) 不相交的路径数就是:(sum-h[x]-h[y]+g[x]+g[y])

其中 (sum,g,h) 均可 dfs 一遍得到。

至于 (f),我们可以在点分治之前,先以 (1) 为根。

对每个点 (u) 算出 (f_{in}[u]),表示 (u) 子树内同色路径数。再算出 (f_{out}[u]) 表示 (u) 子树外同色路径数,并记下此时 (u) 的父节点 (fa[u])

(f_{in}[u])(f_{out}[u]) 只和 (u) 子树内每种颜色的点数有关,可以启发式合并。

(G) 为根时,若 (u) 的父亲还是 (fa[u]),那么 (f[u]=f_{in}[u]),否则 (f[u]=f_{out}[fa[u]])

显然还是不能直接枚举 (x,y)

考虑枚举 (G) 的子节点,即计算 (G) 的前 (i-1) 个子节点的子树对第 (i) 个子节点的子树中的点的贡献。然后再反过来计算后面的子树对前面的子树的贡献。

对于每个 (y),我们只要知道满足 (c_x=c_y)(x) 的个数,以及 (sum h[x]-g[x]),就可以计算对 (ans_y) 的贡献了。

那么我们记 (C[i]) 表示满足 (c_x=i)(x) 的个数,记 (S[i]) 表示满足 (c_x=i)(sum h[x]-g[x])

枚举到一个 (G) 的子节点 (z) 的时候,先 dfs 一遍 (z) 的子树,用之前的 (C,S) 数组给子树内的点贡献,然后再 dfs 一遍 (z) 的子树,更新 (C,S) 数组。

时间复杂度 (O(nlog n)),空间复杂度 (O(n))

Code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

template <class t>
inline void read(t & res)
{
	char ch;
	while (ch = getchar(), !isdigit(ch));
	res = ch ^ 48;
	while (ch = getchar(), isdigit(ch))
	res = res * 10 + (ch ^ 48);
}

template <class t>
inline void print(t x)
{
	if (x > 9) print(x / 10);
	putchar(x % 10 + 48);
}

const int e = 2e5 + 5, mod = 1e9 + 7;

int col[e], ans[e], n, m, q, adj[e], nxt[e], go[e], sze[e], son[e], num, inv4, fans;
int f[e], g[e], h[e], sum, G, tot, id[e], cnt[e], mx[e], now, c[e], s[e];
int f_in[e], f_out[e], fa[e], sub_f[e];
bool vis[e];
vector<int>ch;

inline void add(int &x, int y)
{
	(x += y) >= mod && (x -= mod);
}

inline void del(int &x, int y)
{
	(x -= y) < 0 && (x += mod);
}

inline int plu(int x, int y)
{
	add(x, y);
	return x;
}

inline int sub(int x, int y)
{
	del(x, y);
	return x;
}

inline int mul(int x, int y)
{
	return (ll)x * y % mod;
}

inline int ksm(int x, int y)
{
	int res = 1;
	while (y)
	{
		if (y & 1) res = (ll)res * x % mod;
		y >>= 1;
		x = (ll)x * x % mod;
	}
	return res;
}

inline void link(int x, int y)
{
	nxt[++num] = adj[x]; adj[x] = num; go[num] = y;
	nxt[++num] = adj[y]; adj[y] = num; go[num] = x;
}

inline void dfs1(int u, int pa)
{
	sze[u] = 1;
	mx[u] = 0;
	id[++tot] = u;
	for (int i = adj[u]; i; i = nxt[i])
	{
		int v = go[i];
		if (v == pa || vis[v]) continue;
		dfs1(v, u);
		sze[u] += sze[v];
		mx[u] = max(mx[u], mx[v]);
	}
}

inline void dfs2(int u, int pa)
{
	sze[u] = 1;
	fa[u] = pa;
	for (int i = adj[u]; i; i = nxt[i])
	{
		int v = go[i];
		if (v == pa) continue;
		dfs2(v, u);
		sze[u] += sze[v];
		if (sze[v] > sze[son[u]]) son[u] = v;
	}
}

inline int c2(int x)
{
	return (ll)x * (x - 1) / 2 % mod;
}

inline void change(int x, int v)
{
	del(now, c2(cnt[x]));
	cnt[x] += v;
	add(now, c2(cnt[x]));
}

inline void dfs4(int u, int pa, int op)
{
	change(col[u], op);
	for (int i = adj[u]; i; i = nxt[i])
	{
		int v = go[i];
		if (v == pa) continue;
		dfs4(v, u, op);
	}
}

inline void dfs3(int u, int pa, bool keep, int op)
{
	int i;
	for (i = adj[u]; i; i = nxt[i])
	{
		int v = go[i];
		if (v == pa || v == son[u]) continue;
		dfs3(v, u, 0, op);
	}
	if (son[u]) dfs3(son[u], u, 1, op);
	change(col[u], op);
	for (i = adj[u]; i; i = nxt[i])
	{
		int v = go[i];
		if (v == pa || v == son[u]) continue;
		dfs4(v, u, op);
	}
	if (op == 1) f_in[u] = now;
	else f_out[u] = now;
	if (!keep) dfs4(u, pa, -op);
}

inline void dfs5(int u, int pa, int now_g, int now_h)
{
	g[u] = now_g; 
	h[u] = now_h;
	if (pa == G) ch.emplace_back(u);
	int sum_f = 0, i;
	for (i = adj[u]; i; i = nxt[i])
	{
		int v = go[i];
		if (v == pa) continue;
		if (fa[v] == u) f[v] = f_in[v];
		else f[v] = f_out[u];
		add(sum_f, f[v]);
	}
	for (i = adj[u]; i; i = nxt[i])
	{
		int v = go[i];
		if (v == pa) continue;
		if (u == G) add(sum, f[v]);
		if (vis[v]) continue;
		if (u == G) dfs5(v, u, 0, f[v]);
		else dfs5(v, u, plu(now_g, sub(sum_f, f[v])), now_h);
	}
	for (i = adj[u]; i; i = nxt[i])
	{
		int v = go[i];
		if (v == pa) continue;
		add(g[u], f[v]);
	}
}

inline void dfs6(int u, int pa, int op)
{
	int x = col[u];
	if (op == 1)
	{
		add(c[x], 1);
		add(s[x], sub(g[u], h[u]));
	}
	else
	{
		add(ans[u], s[x]);
		add(ans[u], mul(c[x], plu(sub(g[u], h[u]), sum)));
	}
	for (int i = adj[u]; i; i = nxt[i])
	{
		int v = go[i];
		if (v == pa || vis[v]) continue;
		dfs6(v, u, op);
	}
}

inline void solve(int rt)
{
	int i;
	tot = now = sum = 0;
	dfs1(rt, 0);	
	for (i = 1; i <= tot; i++)
	{
		int u = id[i], x = col[u];
		g[u] = h[u] = s[x] = c[x] = 0;
		if (max(mx[u], tot - sze[u]) * 2 <= tot) G = u;
	}
	ch.clear();
	dfs5(G, 0, 0, 0);	
	g[G] = h[G] = 0;
	int lenc = ch.size();
	c[col[G]] = 1; s[col[G]] = 0;
	for (i = 0; i < lenc; i++)
	{
		int v = ch[i];
		dfs6(v, G, 2);
		if (i != lenc - 1) dfs6(v, G, 1);
	}
	for (i = 1; i <= tot; i++) c[col[id[i]]] = s[col[id[i]]] = 0;
	for (i = lenc - 1; i >= 0; i--)
	{
		int v = ch[i];
		if (i != lenc - 1) dfs6(v, G, 2);
		dfs6(v, G, 1);
	}
	add(ans[G], s[col[G]]);
	add(ans[G], mul(c[col[G]], sum));
	vis[G] = 1;
	vector<int>sons = ch;
	for (i = 0; i < lenc; i++) solve(sons[i]);
}

int main()
{
	read(n); read(m); read(q);
	int i, x, y;
	for (i = 1; i <= n; i++) read(col[i]);
	for (i = 1; i < n; i++) read(x), read(y), link(x, y);
	dfs2(1, 0);
	dfs3(1, 0, 0, 1);
	for (i = 1; i <= n; i++) change(col[i], 1);
	dfs3(1, 0, 1, -1);
	solve(1);
	for (i = 1; i <= n; i++) add(fans, ans[i]);
	inv4 = ksm(4, mod - 2);
	fans = mul(fans, inv4);
	print(fans); 
	putchar('
');
	while (m--)
	{
		read(x);
		print(sub(fans, ans[x]));
		putchar('
');
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

免责声明:文章转载自《[校内训练]palace(点分治+启发式合并)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇[日常训练]网络(bitset+连通性dp)LOJ#3082「2019 集训队互测 Day 5」小水题(线段树)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

ICPC2018焦作站 H. Can You Solve the Harder Problem?

题意: 给出一个数字串,问所有本质不同的子串的最大值之和 如果没有本质不同的要求,就是用单调栈求出每个数字前后第一个大于它的位置,扫一遍计算即可 现在要本质不同,用后缀数组 按字典序依次计算每个后缀的贡献 对于已经按字典序从小到大排好序的后缀i-1和i来说 以i为子串左端点,[i,height[i]]之间的为子串右端点 的子串已经在以i-1位左端点的字串...

hdu 1255 矩形覆盖面积(面积交)

http://www.cnblogs.com/scau20110726/archive/2013/04/14/3020998.html 面积交和面积并基本上差不多。在面积并里,len[]记录的是覆盖一次或以上的长度。如果想要知道覆盖两次或以上的长度,可以加入一个len2[]数组。 1.col[rt]>=2 : 说明该区间被覆盖两次或以上,那么长度就...

北京清北 综合强化班 Day1

a 【问题描述】你是能看到第一题的 friends呢。—— hja何大爷对字符串十分有研究,于是天出题虐杀 zhx。何大爷今天为 何大爷今天为 字符串定义了新的权值计算方法。一个由小写母组成,被定义为其中出现次数最多的字符减去少。(注 被定义为其中出现次数最多的字符减去少。(注 意,在讨论出现最少的字符时候该必须至一次)何大爷给你一个字符串,何大爷想知道这的...

【opencv.js】访问单个像素

JavaScript 写法类似于 C++ 写法。 相关内容详细介绍请移步官网:【https://docs.opencv.org/3.3.1/de/d06/tutorial_js_basic_ops.html】 at 方法 Mat Type At Manipulation CV_8U ucharAt CV_8S charAt CV_16U u...

bzoj 1009 GT考试

一道好题,利用kmp维护递推再更新矩阵乘法 这题首先可以递推: 设状态f[i][j]表示长串更新到了i位置,已经匹配短串匹配了j个数 那么我们有转移: f[i][get_nxt(j)]+=f[i-1][j-1] 当然,你并不懂这是什么意思 我们挨个解释一下 主题思想就是在前面放好的j-1个字符的基础上再放一个字符,看看会发生什么 首先,这里应用的是kmp的n...

SQL2005数据库行列转换

注意:列转行的方法可能是我独创的了,呵呵,因为在网上找不到哦,全部是我自己写的,用到了系统的SysColumns (一)行转列的方法 先说说行转列的方法,这个就比较好想了,利用拼sql和case when解决即可 实现目的 1:建立测试用的数据库 CREATE TABLE RowTest( [Name] [nvarchar](10) NULL...