【题解】Arpa's letter-marked tree and Mehrdad's Dokhtar-kosh paths Codeforces 741D DSU on Tree

Prelude

很好的模板题。

传送到Codeforces：(*￣3￣)╭

Solution

首先要会DSU on Tree，不会的看这里：(❤ ω ❤)。

众所周知DSU on Tree是可以用来处理子树信息的，但是有时候也可以用来处理链上信息。

IOI 2011 Race是一道著名的点分治模板题，要求统计链信息，也可以用DSU on Tree来做，题目链接在这里：(✿◕‿◕✿)。

基本思路和点分治是一样的，对于每个点u，我们统计出所有经过u的路径的信息。

于是我们有了一个非常好的思路：统计每个点u的时候，我们记录下u的所有子孙节点到u的信息，放在某个数组里面。

以这道题为例子，我们把每个字符串压缩为一个二进制串，然后就可以记录u的每个后继节点到u的路径所形成的字符串。

但是问题来了，我们要保留重儿子的信息，但是节点u和她的重儿子之间有一个字母，我们要把这个字母加到重儿子的所有后继节点上，这不是就退化成了暴力了么？

对于IOI 2011 Race这样的题，我们可以选择用数据结构维护，于是复杂度多了一个log。

当然还有更简单的做法，对于本题和IOI 2011 Race这样的题，链上的信息是可减的，于是我们可以不保存“后继节点到点u”的信息，而是保存“后继节点到根”的信息，然后在统计的时候再减去“u到根的信息”。

每个节点到根的信息是不会变的，就不需要维护了，又因为路径信息可减，所以处理起来也很方便。

当然，对于不可减的路径信息，可以选择用数据结构维护。

当然，如果维护不了的话还是写好写好调的点分治吧qwq。

Code

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

const int MAXN = 500010;

const int INF = 0x3f3f3f3f;

int _w;

int n, ans[MAXN];

namespace G {

	int head[MAXN], nxt[MAXN], to[MAXN], val[MAXN], eid;

	void init() {

		memset(head, -1, sizeof head);

	}

	void adde( int u, int v, int w ) {

		to[eid] = v, val[eid] = w;

		nxt[eid] = head[u], head[u] = eid++;

	}

}

int sz[MAXN], dep[MAXN], pa[MAXN], son[MAXN], str[MAXN];

int prelude( int u, int fa, int d, int s ) {

	using namespace G;

	sz[u] = 1, dep[u] = d, pa[u] = fa, str[u] = s;

	for( int i = head[u]; ~i; i = nxt[i] ) {

		int v = to[i], t = 1<<val[i];

		sz[u] += prelude(v, u, d+1, s^t);

		if( sz[v] > sz[son[u]] )

			son[u] = v;

	}

	return sz[u];

}

int maxd[1<<22];

void ans_node( int s, int d, int &ans ) {

	ans = max(ans, d + maxd[s]);

	for( int i = 0; i < 22; ++i )

		ans = max(ans, d + maxd[s^(1<<i)]);

}

void dfs_ans( int u, int &ans ) {

	using namespace G;

	ans_node(str[u], dep[u], ans);

	for( int i = head[u]; ~i; i = nxt[i] )

		dfs_ans(to[i], ans);

}

void ins_node( int s, int d ) {

	maxd[s] = max(maxd[s], d);

}

void dfs_ins( int u ) {

	using namespace G;

	ins_node(str[u], dep[u]);

	for( int i = head[u]; ~i; i = nxt[i] )

		dfs_ins(to[i]);

}

void del_node( int s ) {

	maxd[s] = -INF;

}

void dfs_del( int u ) {

	using namespace G;

	del_node(str[u]);

	for( int i = head[u]; ~i; i = nxt[i] )

		dfs_del(to[i]);

}

void solve( int u, bool clr ) {

	using namespace G;

	for( int i = head[u]; ~i; i = nxt[i] )

		if( to[i] != son[u] )

			solve(to[i], 1);

	if( son[u] ) solve(son[u], 0);

	ans_node(str[u], dep[u], ans[u]);

	ins_node(str[u], dep[u]);

	for( int i = head[u]; ~i; i = nxt[i] )

		if( to[i] != son[u] ) {

			dfs_ans(to[i], ans[u]);

			dfs_ins(to[i]);

		}

	if( clr ) dfs_del(u);

	ans[u] -= dep[u] + dep[u];

	for( int i = head[u]; ~i; i = nxt[i] )

		ans[u] = max(ans[u], ans[to[i]]);

	ans[u] = max(ans[u], 0);

}

int main() {

	_w = scanf( "%d", &n );

	G::init();

	for( int i = 2; i <= n; ++i ) {

		int pa;

		char ch;

		_w = scanf( "%d %c", &pa, &ch );

		G::adde(pa, i, ch - 'a');

	}

	for( int i = 0; i < (1<<22); ++i )

		maxd[i] = -INF;

	prelude(1, 0, 1, 0), solve(1, 0);

	for( int i = 1; i <= n; ++i )

		printf( "%d ", ans[i] );

	puts("");

	return 0;

}

巴特西

【题解】Arpa's letter-marked tree and Mehrdad's Dokhtar-kosh paths Codeforces 741D DSU on Tree

Prelude

Solution

Code

最新文章

热门文章