P3237 [HNOI2014] 米特运输 题目大意 有一棵有 n n n个节点的树，每个点有一个权值，要求修改一些点的权值，使得： 同一个父亲节点的所有儿子节点的权值相同父亲节点的权值必须是所有儿子结点的权值之和 求需要修改的最小次数。 1 ≤ n ≤ 5 × 1 0 5 1\leq n\leq 5\times 10^5 1≤n≤5×105 题解 我们发现，当树上一个点的权值

这玩意好难啊Orz 完全不理解那个模拟深搜到底是什么鬼 果然像我这样的人最好早点滚粗  要简历虚树 首先要选出虚树里面的点 那么关键点和关键点的LCA都要加入到虚树中来 那我们就深搜一遍 处理出每个节点的dfn值和儿子数  按照dfn值依次枚举每一个关键节点 这样可以把同一棵子树内的节点一起找到 用一个深度单调的栈来维护树中的节点 每次取出一个关键点 求出它和栈顶元素的lca  如果

正解:字符串hash 解题报告: 传送门! 字符串hash是字符串匹配中很常见的一个方法,原理也很好懂,这里就不做太多阐述辣有时间放到hash笔记里面去QAQ 题意不说了挺好理解的,自带一句话概括好评 然后直接说正解QAQ 首先要想到对于读入,有三种情况 第一种,麻油有通配符的,这种最简单,直接读的时候判断一下就好 第二种,全都有通配符,显然这样的情况下,只要前后缀都是一样的,中间一定能用通配符