爱飞鱼的blog

树上任意两节点之间最长的简单路径即为树的「直径」。 树形 DP的做法 可以在存在负权边的情况下求解出树的直径。 123456789101112131415161718192021222324252627const int N=10010,M=20010;int n,a,b,c,ans;struct edge{int v,w;};vector<edge> e[N];int dfs(int x,int fa){ int d1=0,d2=0; for(auto ed : e[x]){ int y=ed.v, z=ed.w; if(y==fa) continue;//这样就不用开vis数组了，节约空间 int d=dfs(y,x)+z; if(d>=d1) d2=d1,d1=d; else if(d>d2) d2=d; } ans=max(ans,d1+d2); return d1;//返回从u点往下走的最大长度（悬挂在u点上的最长路径的长度）}int...

请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。这个点被称为树的中心。 题解：https://www.cnblogs.com/dx123/p/17302104.html 评测：https://www.acwing.com/problem/content/1075/ 暴力做法是以每个点为根，求出从根向下走的最远距离，这个过程需要做n遍，每一遍dfs的复杂度是O（n),时间复杂度是O（n^2),考虑优化。 https://oi-wiki.org/dp/tree/#换根-dp 树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。 通常需要两次 DFS，第一次 DFS 预处理诸如深度，点权和之类的信息，在第二次 DFS 开始运行换根动态规划。 算法讲解： 第一次dfs和求树的直径的时候一样，通过递归从下而上得到从...

N,M,S，分别表示树的结点个数、询问的个数和树根结点 理论时间复杂度上界就是O（2n+mlogn） 12345678910111213141516171819202122232425262728293031323334353637383940414243444546const int N=500010;int n,m,s,a,b;vector<int> e[N];int fa[N],son[N],dep[N],siz[N];int top[N];void dfs1(int u,int f){ //搞fa,dep,son fa[u]=f;siz[u]=1;dep[u]=dep[f]+1; for(int v:e[u]){ if(v==f) continue; dfs1(v,u); siz[u]+=siz[v]; if(siz[son[u]]<siz[v])son[u]=v; }}void dfs2(int u,int t){ //搞top top[u]=t; //记录链头 ...

专题班树型dp练习https://ac.nowcoder.com/acm/contest/28260#question 原问题求树上的最大独立集 Solution：仔细读题，一开始以为每次选择的地点是连续的，导致求成最大深度了。实际上是最大独立集。 debug：对于每个儿子的贡献需要累加，叶子节点需要赋初值。 12345678910111213141516171819202122232425vector<int>e[N];int dp[N][2];void dfs(int u,int fa){ dp[u][1]=1;//叶节点赋值和每个点本身贡献 for(auto v:e[u]){ if(v==fa)continue; dfs(v,u); dp[u][1]+=dp[v][0];//有多个叶子，应该是+=，不是+ dp[u][0]+=max(dp[v][1],dp[v][0]); } }void solve(){ int rt;cin>>n>>rt; for(int...

一些定义和核心性质，对于算法理解有很大帮助,不妨考虑字符串全部为1base1base1base Border:若字符串S的prefix[i]=suffix[i]prefix[i]=suffix[i]prefix[i]=suffix[i]，则称这个前缀或者这个后缀是一个border 周期：对于字符串S，存在整数P满足S[i]=S[i−P]S[i]=S[i-P]S[i]=S[i−P](p<i≤∣S∣)(p<i \le |S| )(p<i≤∣S∣),则P为字符串S的一个周期。这里的周期也常被称为循环覆盖。 循环节：若字符串S的周期P满足p ∣ s.size()p\,|\, s.size()p∣s.size(),则P是S的一个循环节。 理解：周期用循环覆盖理解，就是长度P的周期拼接若干次以后，S一定作为这其中的子串出现。对于循环节来说，循环节拼接若干次以后，恰好能够得到S。 性质： P是S的周期⇔\Leftrightarrow⇔...

子序列自动机 判断s是不是t的子序列 123456789101112131415161718192021bool isSubsequence(string s, string t) { int m = t.size(); vector<array<int, 26>> next(m + 2); t = " " + t; for (int i = m; i >= 1; i--) { for (int j = 0; j < 26; j++) { if (j == t[i] - 'a') next[i][j] = i + 1; else { next[i][j] = next[i + 1][j]; } } } int p = 1; for (auto...

最小表示法 有一个长度为 nnn的字符串 s，如果我们不断把它开头的字符移到结尾，可以得到 n个字符串，这些字符串是循环同构的，其中字典序最小的就是 s的最小表示。 123456789101112131415161718string getmin(string s){ int len=s.size(); s+=s; s=" "+s; int i=1,j=2;//i,j表示以其位置开头的循环串 while(j<=len){ int k=0;//时间复杂度线性 while(k<len&&s[i+k]==s[j+k])k++; if(s[i+k]>s[j+k]){ i+=k+1; } else j+=k+1; if(i==j)j++; if(i>j)swap(i,j); } //最终字典序最小的是以i开头的 return s.substr(i,len);} P1368...

题目描述 给出两个字符串 s1s_1s1​ 和 s2s_2s2​，若 s1s_1s1​ 的区间 [l,r][l, r][l,r] 子串与 s2s_2s2​ 完全相同，则称 s2s_2s2​ 在 s1s_1s1​ 中出现了，其出现位置为 lll。 现在请你求出 s2s_2s2​ 在 s1s_1s1​ 中所有出现的位置。 定义一个字符串 sss 的 border 为 sss 的一个非 sss 本身的子串 ttt，满足 ttt 既是 sss 的前缀，又是 sss 的后缀。 对于 s2s_2s2​，你还需要求出对于其每个前缀 s′s's′ 的最长 border t′t't′ 的长度。 输入格式 第一行为一个字符串，即为 s1s_1s1​。 第二行为一个字符串，即为 s2s_2s2​。 输出格式 首先输出若干行，每行一个整数，按从小到大的顺序输出 s2s_2s2​ 在 s1s_1s1​ 中出现的位置。 最后一行输出 ∣s2∣|s_2|∣s2​∣ 个整数，第 iii 个整数表示 s2s_2s2​ 的长度为 iii 的前缀的最长 border 长度。 样例 #1 样例输入...

Z函数——拓展KMP 算法作用：(考虑1base)求文本串 T 的每一个后缀与模式串 M 的最长公共前缀长度。核心数组z[i]就表示lcp(s[i:end],s[1:n])lcp(s[i:end],s[1:n])lcp(s[i:end],s[1:n]) 模板： 1.传的是0base串，函数内部会处理。 2.其次一般来说前面是模式串，间隔一个$分隔符后是文本串。这样就是可以知道文本串中出现了多少次模式串。 z函数的求解： 1234567891011121314151617181920vector<int> exkmp(string s){ int len=s.size(); s=" "+s; vector<int> z(len+1); z[1]=0; int l=1,r=0; for(int i=2;i<=len;i++){ if(i>r)z[i]=0; else {//利用之前的信息 int...

两个正整数a，b，请问a∗b有哪些因子 1≤a,b≤1e9 求因子的数量并给出所有因子 本题无脑的暴力显然不能过，但用set存数，加上考虑到a*b的所有约数其实就是a的所有约数和b的所有约数分别相乘(核心） 补充常识：int范围内数的约数个数最多为1600，2e9数的约数个数最多为1536，这也是本题能这样暴力的基础 https://blog.csdn.net/qq_40438165/article/details/122030763 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include <bits/stdc++.h>using namespace std;# define int long longconst int N = 1e5 + 10;const int M = 2e5 + 10;const int inf = 0x3f3f3f3f;const int mod = 998244353;int n,...