Za
yyb Fibonacci的性质
-
(gcd(f[i],f[i+1])=1)
证明
(gcd(f[i],f[i+1]))
(=gcd(f[i+1]-f[i],f[i]))
(=gcd(f[i-1],f[i]))
(=....)
(=gcd(f[1],f[2])=1)) -
(f[m+n]=f[m−1]f[n]+f[m]f[n+1]f[m+n]=f[m−1]f[n]+f[m]f[n+1])
-
(gcd(f[n+m],f[n])=gcd(f[n],f[m])gcd(f[n+m],f[n])=gcd(f[n],f[m]))
由上面式子得到
(gcd(f[n+m]=f[m−1]f[n]+f[m]f[n+1],f[n])gcd(f[n+m]=f[m−1]f[n]+f[m]f[n+1],f[n]))
(=gcd(f[n+1]f[m],f[n])=gcd(f[n+1]f[m],f[n]))
(=gcd(f[n+1],f[n])∗gcd(f[m],f[n])=gcd(f[n+1],f[n])∗gcd(f[m],f[n]))
(=1∗gcd(f[m],f[n])=1∗gcd(f[m],f[n]))
(=gcd(f[m],f[n])) -
(gcd(f[n],f[n+m])=f[gcd(n,n+m)]gcd(f[n],f[n+m])=f[gcd(n,n+m)])
证明
(gcd(f[n],f[n+m])gcd(f[n],f[n+m]))
(=gcd(f[n],f[n+m]%f[m])=gcd(f[n],f[n+m]%f[m]))
(=gcd(f[n],f[m])=gcd(f[n],f[m]))
(=gcd(f[n],f[(n+m)%n])=gcd(f[n],f[(n+m)%n]))
这是辗转相除的形式
所以，最后有
(gcd(f[n],f[n+m])gcd(f[n],f[n+m]))
(=gcd(f[0],f[gcd(n,n+m)])=gcd(f[0],f[gcd(n,n+m)]))
(=f[gcd(n,n+m)])
图论基础
(一些现在知道但不太清楚(?)or确定的
简单路径：simple path，是每条边只经过了一次的路径。
简单回路：图的定点序列中，除了起点和终点相同外，其余顶点不重复的回路。
图连通：如果无向图 中任意两个节点连通，称其为是连通的。
强连通：有向图 强连通是指， 中任意两个节点连通。
弱连通：有向图 弱连通是指， 中的所有边替换为无向边后， 为连通图。
点连通度：一张图的点连通度的大小等于最小点割集的大小。
边连通度：一张图的边连通度的大小等于最小边割集的大小。
点割集：设图(G=<V,E>)，若存在 (V'subset V)且(V'
ot=oslash)，使得(p(G-V')>p(G))，而对于任意的(V"subset V')，均有(p(G-V')=p(G))，则称 (V')是(G)的点割集。特别地，若(V')是(G)的点割集，且(V')是单元集，即(V'={v})，则称(v)为 割点
（(p(G))表示图(G)的连通分支（连通块）的个数）
边割集：设图(G=<V,E>)，(E'subset E)且(E' ot=oslash)，使得(ps(G-E')>p(G))，而对于任意的(E''subset E')，均有(p(G-E'')=p(G))，则称(E') 是(G)的边割集（或简称为割集）。特别地，若(E')是(G)的边割集，且(E')是单元集，即(E'={e})，则称(e)为桥。
（ (p(G))表示图 G 的连通分支（连通块）的个数）
子图：选取一个节点的子集和边的子集构成的图。
生成子图：选取的子图的节点和原图一样。
导出子图：选取一个节点的子集，再选取这些节点相关联的边的集合构成的图。
边导出子图：选取一个边的子集，再选取这些边相关联的节点的集合，构成的图。
连通子图：（一个无向图的）连通的子图。
连通分量：（一个无向图的）极大的连通子图。
【注】：极大是指添加任何节点或者边后都不再满足。
树基础
有根二叉树（rooted binary tree） ：每个结点最多只有两个儿子（子结点）的有根树称为二叉树。常常对两个子结点的顺序加以区分，分别称之为左子结点和右子结点。
大多数情况下， 二叉树 一词均指有根二叉树。
完整二叉树（full/proper binary tree） ：每个结点的子结点数量均为 0 或者 2 的二叉树。换言之，每个结点或者是树叶，或者左右子树均非空。
完全二叉树（complete binary tree） ：只有最下面两层结点的度数可以小于 2，且最下面一层的结点都集中在该层最左边的连续位置上。
完美二叉树（perfect binary tree） ：所有叶结点的深度均相同的二叉树称为完美二叉树。
先序遍历：先访问根，再访问子节点。
中序遍历：先访问左子树，再访问根，再访问右子树。
后序遍历：先访问子节点，再访问根。
已知中序遍历和另外一个可以求第三个。
树的重心
定义：以树的重心为根时，所有的子树（不算整个树自身）的大小都不超过整个树大小的一半。
找到一个点，其所有的子树中最大的子树节点数最少，那么这个点就是这棵树的重心。
删去重心后，生成的多棵树尽可能平衡。
性质：
- 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。
- 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两个树的重心的路径上。
- 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离
- 一棵树最多有两个重心，且相邻。
求法：
树的重心可以通过简单的两次搜索求出。
- 第一遍搜索求出以每个节点为根的子树中结点数量(sz_u)
- 第二遍搜索找出使(max_{vin son(u)}{n-sz_u,sz_v})最小的节点
int ans,siz=inf;
void dfs(int u,int fa){
sz[u]=1;
int res=0;
for(int i=head[u],v;i;i=e[i].nxt){
if((v=e[i].v)==fa) continue;
dfs(v,u),sz[u]+=sz[v];
res=max(res,son[v]);
}
res=max(res,n-sz[u]);
if(res<siz) ans=u,siz=res;
}
淀粉质点分治
学长：
淀粉质一般用于处理树上路径问题
淀粉质的本质是对整棵树进行重心分治
然后乱搞
选择重心作为当前分治点，将整棵树分开，各个子树互不影响，再递归到子树中进行分治，所有分治点构成一棵树
why重心？
考虑分治时的问题规模，只有选择重心时，才能使得子问题的规模尽量小，重心的每个子树大小都不会超过 n/2 , 即每次递归问题规模至少减一半，只用递归log层
inline void findrt(int x,int fa){//找重心
siz[x]=1; bst[x]=0;
for(rg int i=hd[x];i!=-1;i=e[i].nt){
int v=e[i].v; if(v == fa || vis[v]) continue;
findrt(v,x); siz[x]+=siz[v];
bst[x]=max(bst[x],siz[v]);
}
bst[x]=max(bst[x],S-siz[x]);
if(bst[x] < bst[rt] || rt == 0) rt=x;
}
假设你已经找出了重心，该怎么做 ？
暴力啊
考虑统计所有经过当前重心且在当前分治范围内的路径((u,v))都可以看作((u,S)+(S,v))
题目要求统计长为k的路径，我们可以硬枚举两条边，统计进一个全局数组中，然后继续分治，这样做的话对于一条路径，只会在其经过的最高分治点被统计，O(n^2)
好像统计了一些不该统计的东西 ？
这样会统计到来自于同一子树的两条路径，并不合法，
考虑在每次分治一棵子树前，先减掉这棵树内不合法的情况，同样O(n^2)
照着学长代码打的模板
#include<bits/stdc++.h>
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
const int N=1e4+5;
int k[10000005];
int n,m,dis[N],vis[N],rt,sz[N],bst[N],S,tt,q[N];
template <class t>void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
int tot,head[N];
struct edge{int v,w,nxt;}e[N<<1];
inline void add(int u,int v,int w){
e[++tot]=(edge){v,w,head[u]},head[u]=tot;
}
inline void findrt(int u,int fa){
sz[u]=1,bst[u]=0;
for(int i=head[u],v;i;i=e[i].nxt){
if(vis[v=e[i].v]||v==fa) continue;
findrt(v,u),sz[u]+=sz[v];
bst[u]=Max(bst[u],sz[v]);
}
bst[u]=Max(bst[u],S-sz[u]);
if(bst[u]<bst[rt]||!rt) rt=u;
}
inline void getdis(int u,int fa){
q[++tt]=dis[u];
for(int i=head[u],v;i;i=e[i].nxt){
if(vis[v=e[i].v]||v==fa) continue;
dis[v]=dis[u]+e[i].w,getdis(v,u);
}
}
inline void deal(int u,int la,int fl){
dis[u]=la,tt=0,getdis(u,0);
for(int i=1;i<=tt;++i)
for(int j=1;j<=tt;++j)
k[q[i]+q[j]]+=fl;
}
inline void getans(int u){
vis[u]=1,deal(u,0,1);
for(int i=head[u],v;i;i=e[i].nxt){
if(vis[v=e[i].v]) continue;
deal(v,e[i].w,-1);
rt=0,S=sz[v],findrt(v,u);
getans(rt);
}
}
int main(){
freopen("in.txt","r",stdin);
rd(n),rd(m);
for(int i=1,u,v,w;i<n;++i) rd(u),rd(v),rd(w),add(u,v,w),add(v,u,w);
S=n,findrt(1,0);
getans(rt);
for(int i=1,x;i<=m;++i){
rd(x);
if(k[x]>0) puts("AYE");
else puts("NAY");
}
return 0;
}
kruskal
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5,M=5e5+5,inf=0x3f3f3f3f;
int n,m;
ll ans=0;
template<class t>void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
struct edge{
int u,v,w;
bool operator<(const edge&X)const{return w<X.w;}
}e[M];
int f[N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void kruskal(){
for(int i=1;i<=n;++i) f[i]=i;
for(int i=1,u,v;i<=m;++i)
if(find(u=e[i].u)!=find(v=e[i].v)) f[f[u]]=f[v],ans+=e[i].w;
}
int main(){
rd(n),rd(m);
for(int i=1,u,v,w;i<=m;++i) rd(u),rd(v),rd(w),e[i]=(edge){u,v,w};
sort(e+1,e+m+1);
kruskal();
printf("%lld",ans);
return 0;
}
prim
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int>pii;
priority_queue<pii,vector<pii>,greater<pii> >q;
const int N=2e5+5,M=5e5+5,inf=0x3f3f3f3f;
int n,m;
ll ans=0;
template<class t>void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
int head[N],tot=0;
struct edge{int v,w,nxt;}e[M<<1];
void add(int u,int v,int w){
e[++tot]=(edge){v,w,head[u]},head[u]=tot;
}
int dis[N],vis[N];
void prim(){
memset(vis,0,sizeof(vis));
memset(dis,inf,sizeof(dis));
q.push(make_pair(dis[1]=0,1));
while(!q.empty()){
int u=q.top().second;q.pop();
if(vis[u]) continue;
ans+=dis[u],vis[u]=1;
for(int i=head[u],v,w;i;i=e[i].nxt)
if(!vis[v=e[i].v]&&dis[v]>(w=e[i].w))
dis[v]=w,q.push(make_pair(dis[v],v));
}
}
int main(){
rd(n),rd(m);
for(int i=1,u,v,w;i<=m;++i) rd(u),rd(v),rd(w),add(u,v,w),add(v,u,w);
prim();
printf("%lld",ans);
return 0;
}