图论

四种实现 实现模式长处毛病邻接矩阵实现简略，可求任意顶点的出度和入度在存储稠密图时会造成空间节约邻接表应用数组链表实现，不会造成空间节约不能同时求出任意顶点的出度和入度，除非同时构建邻接表和逆邻接表。对边进行操作时须要操作两次十字链表应用数组链表实现，不会造成空间节约，能够求出某个顶点的入度和出度对边进行操作时须要操作两次邻接多重表对边的操作进行了优化：操作边时由两次缩小到了一次删除操作较为简单

P3258 [JLOI2014]松鼠的新家：https://www.luogu.com.cn/prob...树剖+线段树 #include <algorithm>#include <iostream>#include <stdio.h>#include <string.h>#define lson now<<1#define rson now<<1|1using namespace std;const int N = 300010;int a[N];int n;int head[N],nex[2*N],to[2*N],idx;int u,v;void add(int u,int v){ to[idx]=v; nex[idx]=head[u]; head[u]=idx++;}struct node{ long long int val; int lazy;}tree[4*N];int fa[N],deep[N],id[N],top[N],size[N],son[N];int cnt;//dfs序编号void dfs(int x,int f)//工夫复杂度为O(2*m){ fa[x]=f; size[x]=1; deep[x]=deep[f]+1; for(int i=head[x];~i;i=nex[i]) { int j=to[i]; if(j==f) { continue; } dfs(j,x); size[x]+=size[j]; if(size[j]>size[son[x]]) { son[x]=j; } }}void dfs2(int x,int t)//工夫复杂度大概为O(2*m){ top[x]=t; id[x]=++cnt; if(!son[x]) { return; } dfs2(son[x],t); for(int i=head[x];~i;i=nex[i]) { int j=to[i]; if(j==fa[x]||j==son[x]) { continue; } dfs2(j,j); }}void pushdown(int now,int l,int r){ int ly=tree[now].lazy; tree[lson].lazy += ly; tree[rson].lazy += ly; int mid = (l+r)>>1; tree[lson].val += 1ll*(l-mid+1)*(1ll*ly); tree[rson].val += 1ll*(r-mid)*(1ll*ly); tree[now].lazy = 0;}void pushup(int now){ tree[now].val = tree[lson].val + tree[rson].val;}void update(int now,int l,int r,int al,int ar,int val){ if(al<=l&&ar>=r) { tree[now].val += 1ll*(r-l+1)*(1ll*val); tree[now].lazy += val; return; } if(tree[now].lazy!=0) { pushdown(now,l,r); } int mid = (l+r)>>1; if(al>mid) { update(rson,mid+1,r,al,ar,val); } else if(ar<=mid) { update(lson,l,mid,al,ar,val); } else { update(rson,mid+1,r,al,ar,val); update(lson,l,mid,al,ar,val); } pushup(now);}int query(int now,int l,int r,int al,int ar){ if(al<=l&&ar>=r) { return tree[now].val; } if(tree[now].lazy!=0) { pushdown(now,l,r); } int mid = (l+r)>>1; long long int res = 0; if(al>mid) { res += query(rson,mid+1,r,al,ar); } else if(ar<=mid) { res += query(lson,l,mid,al,ar); } else { res += query(rson,mid+1,r,al,ar); res += query(lson,l,mid,al,ar); } return res;}void LCA(int x,int y){ int fx=top[x],fy=top[y]; while(fx!=fy) { if(deep[fx]>=deep[fy]) { update(1,1,n,id[fx],id[x],1); x=fa[fx]; fx=top[x]; } else { update(1,1,n,id[fy],id[y],1); y=fa[fy]; fy=top[y]; } } if(deep[x]<deep[y]) { swap(x,y); } update(1,1,n,id[y],id[x],1);}int main(){ scanf("%d",&n); memset(head,-1,sizeof(head)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=0;i<n-1;i++) { scanf("%d %d",&u,&v); add(u,v); add(v,u); } dfs(1,0); dfs2(1,1); for(int i=1;i<n;i++) { LCA(a[i],a[i+1]); } for(int i=1;i<=n;i++) { long long ans = query(1,1,n,id[i],id[i]); if(i!=a[1]) { ans --; } printf("%lld\n",ans); } return 0;}树上差分 ...

求最近公共先人的几种办法1.向上标记法（暴力做法，不罕用）工夫复杂度为O(n)，最坏状况下为一条链；求4和6的最近公共先人：首先建设一个bool类型的数组用来标记4或者6的先人，比方，4的先人是2,1（从下往上顺次遍历并标记），那就将2,1标记为1，之后标记6的先人，在标记过程中如果遇到已被标记的先人，那么这个先人就是4和6的公共先人，在本例中为1。 2.倍增法（罕用）fa[i,j]示意从i开始，向上走2^j步所能走到的节点。0<=j<=logn,depth[i]示意深度步骤：哨兵：如果从i节点跳2^j次方步会跳过根节点，那么fai=0（非凡标记），规定depth[0]=0;【1】先将两个点跳到同一层例如：如上图，要从x节点跳到与y节点同一高度当初已知depth[x]和depth[y]假如t=depth[x]-depth[y]，为x与y之间的高度差；利用二进制拼凑的思维，假如t=11,先找到小于等于11的最大的2的整数幂，也就是8，那么11-8=3，接下来再找到小于等于3的最大的2的整数次幂，也就是2，那么3-2=1，之后再找到小于等于1的2的整数次幂，也就是2^0=1，那么1-1=0，就拼凑好了t。要害局部代码：//depth代表节点深度，fai代表节点i向上跳2^j步的节点编号 for(int i=15;i>=0;i--) { if(depth[fa[u][i]]>=depth[v]) { u=fa[u][i]; } }【2】让两个同时往上跳，始终跳到它们的最近公共先人的下一层。预处理O(nlogn)查问O(logn) for(int i=15;i>=0;i--) { if(fa[u][i]!=fa[v][i]) { u=fa[u][i]; v=fa[v][i]; } }