一个比较有趣的树形DP，情况比较多。【题目简述】给定一棵树，求三条相连的边，其边权之和最大。【思路】以X代表当前节点，S表示儿子，G表示孙子，P表示父节点。首先把树建出来，在以下图中，我们模拟二号点的DP过程，考虑以下几种情况：有一条边指向父节点时FG（FatherGrandson）：一

首先，我们会有一个很简单的想法，枚举断边，产生两棵子树，然后在两棵树内分别求带权重心，计算贡献，这样的话复杂度是\(O(n^2)\)的。那么我们要好好利用$h\leq100$的性质。考虑\(sze[u]\)为带权重量，\(g[u]\)为以\(u\)为根的树，所有点都到\(u\)的代价。所以\(g[u]=\sum\l

题目传送门前置知识动态树分治|动态开点线段树|标记永久化解法考虑动态点分治。两种操作本质上是将luoguP6329【模板】点分树|震波的操作互换了下，将原需支持单点修改、区间查询的数据结构换成需支持区间修改、单点查询的数据结构即可。区间修改、单点查询的动态开

虚树VirtualTree学习笔记引入P2495[SDOI2011]消耗战题目大意：给一棵\(n\)个点的树，\(m\)次询问\(k\)个点，要求切断一些边使点1不可达这些点，求最小切断的边权和。\(n\le2.5*10^5,m\le5*10^5,\sumk\le5*10^5\)先考虑一个朴素的DP，每次询问扫一遍整个树。设\(f_

题目描述维护一个字符串集合，支持两种操作：I x 向集合中插入一个字符串 x；Q x 询问一个字符串在集合中出现了多少次。共有 N (1≤N≤2×10^4) 个操作，输入的字符串总长度不超过 10^5，字符串仅包含小写英文字母。输入格式第一行包含整数 N，表示操作数。接下来 N 行，

Statement树，每个点有一个颜色，初始每个点颜色互不相同到根链涂上新颜色链颜色数\(u\)子树内点\(v\)到根路径的最多颜色数Solution首先，相同颜色的点一定构成一条从下往上的链考虑LCT，维护一个性质：一条实链的点的颜色相同.于是\(u\)到根的颜色数\(=\)\(u\)到根的虚

目录结对项目1.PSP2.1表格2.性能分析3.设计实现过程1.结构1.number2.函数1.solve()2.create()3.getstring()4.pplus(strings)5.check(strings)6.read(strings)7.work(vectorpro)8.write1(vectorans)9.compare(vectorans,vectorans1)10.write2(vectorright,vectorwron

零、前言对于模式串匹配问题，在很多基础的数据结构课程中都有涉及到，如KMP算法，BM算法，Trie。但是给定文本串，我们有多个模式串要去查询。难道要多次调用KMP/BM，或者在Trie上多次查询吗？Aho和Corasick基于Trie，对KMP进行了推广，使得Trie可以在一个文本串中识别一个关

单例模式（饿汉和懒汉）//饿汉式单例模式includeusingnamespacestd;classson{public:son(constson&)=delete;son&operator=(constson&)=delete;son(constson&&)=delete;son&operator=(constson&&)=delete;staticson&getinsta

题目思路将每一个输出的串放入一个Trie树中。考虑离线处理询问\((x,y)\)，对于每一个\(y\)集中处理所有的\(x\)，\(y\)在Trie树上走，走过的点标记一下，结果就是\(x\)字符串结尾节点在fail树上的对应节点的子树的标记数量。记得在节点离开的时候撤销标记。代码#incl

最高乘法得分动态规划解决从数组b中选择下标的问题题目描述给你一个大小为4的整数数组a和一个大小至少为4的整数数组b。你需要从数组b中选择四个下标i0,i1,i2,和i3，并且要求满足i0<i1<i2<i3。你的得分将是：a[0]*b[i0]+a[1]*b[i1]+a[2]*b

首先不难发现，确定了根以后答案是固定的。设\(sz_i\)表示以1为根的树中，以1为根的子树大小；\(f_i\)表示以1为根的树中，以\(i\)为根的子树得到的最大权值，可以得到转移\[f_u=sz_u+\sum_{v\inson_u}f_v\]然后设\(g_v\)表示先选\(v\)的最大权值，\(v\)的父亲为\(

Splay树定义Splay树是一个二叉平衡搜索树，它可以通过Splay操作将一个结点旋转至根结点或者一个给定的结点的下一层，使得整棵树仍然满足二叉搜索树的性质。Splay树可以在均摊\(O(\logn)\)的时间内完成查找、插入、查询、删除等操作。二叉搜索树的定义：空树是一个二叉

[COCI2020-2021#3]Vlak题意Nina和Emilija在玩游戏。Nina先手，两人轮流在纸上写下一个字母。每个玩家写下字母后得到的单词必须是该玩家喜欢的歌曲中某个单词的前缀。不能操作的玩家输，判断最后谁会赢。思路对每个玩家喜欢的歌曲建立字典树。搜索每个玩家的操作，每次在两

subtask1\(O(2^{n+m})\)暴力，可以获得\(15\)分。subtask2考虑sub1中的check方式就是考虑两点是否存在两条边不重复路径，这启发我们缩ecc。缩掉ecc后进行dp计数。\(dp_{i,0/1}\)代表考虑\(i\)的子树，\(i\)选或不选的方案数。注意由于已经缩掉了ecc，则\(i\)选择

A.牛牛的方程式题目描述给定一个三元一次方程\(ax+by+cz=d\)，求该方程是否存在整数解。思路由于若干个\(a,b,c\)只能凑出\(\gcd(a,b,c)\)的倍数，所以只需判断\(d\)是否为\(\gcd(a,b,c)\)的倍数即可。特别的，若\(a,b,c\)均为\(0\)，则显然只有\(d=0\)时存在整数解。

有一个简单的博弈问题：现在有一颗\(n\)个点的树，每次询问后给出一个点连接的所有子节点。Alice和Bob在树上博弈。Alice和Bob每次可以将点向下移动一格。如果到了叶子节点，便不再移动，交互库给出叶子权值。Alice希望选的数最大，Bob反之。求：到达的数最后是多少？显然有\(

Qoj9111ZayinansString/ABC356E谨以此帖记录一个有意思的Trick题意给了一个长度为\(n\)的目标串\(s\)和\(m\)个模式串每个模式串有一个价值\(v\)要求从\(s\)中选出一个子序列\(t\)，定义\(t\)的价值为他的所有子串的价值和（若该子串没出现在模式串中，那么

首先Trie树：#include<bits/stdc++.h>usingnamespacestd;intT,q,n,t[3000005][65],cnt[3000005],idx;chars[3000005];intgetnum(charx){if(x>='A'&&x<='Z')returnx-'A';elseif(x>='a

CF2002D1.DFSChecker(EasyVersion)（*1900）思维题目链接题意：给你一棵\(n\)个节点组成的完全二叉树，并给出一个排列\(p\)。接下来进行\(q\)次询问。每次询问给你\(x\)和\(y\)，你需要交换\(p_x\)和\(p_y\)。并且回答交换之后的排列\(p\)是否是这棵完全二叉树

电力题意求一个图删除一个点之后，联通块最多有多少。思路先计算出原来有多少个联通块，再计算每个点对联通块的贡献的最大值。考虑跑一遍tarjan，孤立点的贡献为\(-1\)，非割点贡献为\(0\)，割点贡献为dfs树上\(low_v\gedfn_u\)的\(v\)的个数，根的贡献为dfs树上的儿子个数

题意给定一个\(n\)个结点的无向图，初始没有边。接下来有\(m\)个询问，每次向图中加入一条连接\((u,v)\)权值为\(w\)的边。每次加边后，查询是否存在一个边集\(E\)，满足当图中只有\(E\)中的边时，所有点的度数均为奇数。同时你还要最小化\(\max\limits_{(u,v,w)\inE}

https://zhuanlan.zhihu.com/p/560661911数据结构学习笔记(8)启发式合并启发式合并是用来解决子树中的统计问题。在codeforces上叫做dsuontree(树上启发式合并)。这里我们主要是来讲在树上进行启发式合并。实际上之前我有讲过启发式合并严格鸽：启发式合并看似暴力实则很快的

最近在做笔试时碰到这样一道题目publicclassTest{ publicstaticvoidmain(String[]args){ Sonson=newSon(); }}classFather{ static{ System.out.println("A"); } { System.out.println("B"); } Father(){

李超线段树学习笔记模板传送门从模板题就能看出来嗷，李超线段树非常牛逼。\bx从名字中就能看出来嗷，这玩意儿是个线段树。那么考虑在线段树上维护一堆线（一次函数）。对于每个点，存所有线中，使这个线段$mid$的点的线。对于加入一个点，根节点递归，扫到一个点时，若这个点在$mid$