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的更多相关文章
-
dsu on tree学习笔记
前言 一次模拟赛的\(T3\):传送门 只会\(O(n^2)\)的我就\(gg\)了,并且对于题解提供的\(\text{dsu on tree}\)的做法一脸懵逼. 看网上的其他大佬写的笔记,我自己画 ...
-
codeforces 741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths(启发式合并)
codeforces 741D Arpa's letter-marked tree and Mehrdad's Dokhtar-kosh paths 题意 给出一棵树,每条边上有一个字符,字符集大小只 ...
-
CF 741D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths [dsu on tree 类似点分治]
D. Arpa's letter-marked tree and Mehrdad's Dokhtar-kosh paths CF741D 题意: 一棵有根树,边上有字母a~v,求每个子树中最长的边,满 ...
-
Codeforces 741 D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths 思路: 树上启发式合并 从根节点出发到每个位置的每个字符的奇偶性记为每个位 ...
-
CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths 好像这个题只能Dsu On Tree? 有根树点分治 统计子树过x的 ...
-
codeforces 741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
题目链接:Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths 第一次写\(dsu\ on\ tree\),来记录一下 \(dsu\ o ...
-
CF 741 D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths http://codeforces.com/problemset/probl ...
-
【CodeForces】741 D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths(dsu on tree)
[题意]给定n个点的树,每条边有一个小写字母a~v,求每棵子树内的最长回文路径,回文路径定义为路径上所有字母存在一种排列为回文串.n<=5*10^5. [算法]dsu on tree [题解]这 ...
-
CF741 D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
题目意思很清楚了吧,那么我们从重排回文串的性质入手. 很容易得出,只要所有字符出现的次数都为偶数,或者有且只有一个字符出现为奇数就满足要求了. 然后想到什么,Hash?大可不必,可以发现字符\(\in ...
随机推荐
-
JQuery插件开发简单实例
经常使用Jquery的各种插件,却对如何开发插件一无所知,以为是一件很麻烦的事儿?其实不然,下面通过一个简单的实例,来看一下Jquery Plugin的开发. 先看DEMO:动画菜单 不用插件如何实现 ...
-
Android笔记:去除标题栏
1: 在oncreate方法中添加requestWindowFeature(Window.FEATURE_NO_TITLE); 必须在setContentView()之前执行. 2: 在Android ...
-
js原生继承之——构造函数式继承实例
<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8&qu ...
-
Python之旅.第四章.模块与包 4.02
一.模块的使用之import 1 什么是模块?模块就一系统功能的集合体,在python中,一个py文件就是一个模块,比如module.py,其中模块名module2 使用模块2.1 import 导入 ...
-
【编程练习】poj1111
Image Perimeters Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 8632 Accepted: 5168 ...
-
mybatis乱码
单个字段 <property name="url" value="jdbc:mysql://127.0.0.1:3306/db?characterEncoding= ...
-
(后端)项目中的错误之java中判断字符里面含有某些字符
数据库的数据出现了数据错误.找到原因是因为代码里面Spring的判断所导致的.其实就是判断字符里有01,走这里,有02,走那里,全是if,但是是类似indexOf的那种判断,偏偏有一个数据是0102, ...
-
Windows PowerShell 入門(10)-デバッグ編
対象読者 Windows PowerShellでコマンドレット操作ができる方 何らかのプログラミング経験があればなお良い 必要環境 Windows PowerShell デバッグメッセージの出力 Po ...
-
springcloud 入门 8 (config配置中心)
Spring Cloud Config: 配置中心为了方便服务配置文件统一管理,实时更新,所以需要分布式配置中心组件,它就是Spring Cloud Config. 在分布式系统中,由于服务数量巨多, ...
-
java框架篇---hibernate之连接池
Hibernate支持第三方的连接池,官方推荐的连接池是C3P0,Proxool,以及DBCP.在配置连接池时需要注意的有三点: 一.Apche的DBCP在Hibernate2中受支持,但在Hiber ...