View Code
T5太鼓达人：dfs欧拉回路
颓了题解 ， 膜拜soul神佬 。
一看题真的想不出来哪里和图论有关系……查了一下全说打表……
然后刷了一波学长题解 ， 打了dfs过掉了 。（我不是人我颓题解了……）
#include#include#include#include#include#includeusing namespace std;int k,qyqyooo,ans[1<<13];bool vis[(1<<13)+5];inline bool dfs(int x,int len){if(vis[x])return 0;if(len==(1<
View Code
T6天天爱跑步：动态开点线段树+树上差分+LCA
写一个正经题解：
有两个式子 ， 一个是si到LCA路径上满足wj的条件 ， 另一个是在LCA到ti上的 ， 这些大家感性理解一下就好 。
这东西别的博客上都有 ， 我就不放了（懒）我重点补大佬们的坑
首先为了求LCA做准备肯定要写一个dfs 。不过我们还有别的用途 ， 顺手求出dfs序 。
目的是用一个区间来表示一个节点的子树方便后期统计 。
然后对每一个点开一个线段树 ， 线段树里面按照深度存的是当前节点所管辖的子树内的该深度的节点个数——的差分数组 。（请理性的理解这句话三遍）
这很重要 。
#include#include#include#include#include#define rint register intusing namespace std;struct node{int u,v,next;}edge[600005];struct tree{int st,en,go;}lp[300005];int n,tot_e,cnt,m,num,in_x,in_y,first[300005],deep[300005],ldfn[300005],rdfn[300005];int lc[300005<<6],rc[300005<<6],w[300005],p[300005][22],ans[300005],root[300005<<6];int qyqyooo[300005<<6],size[300005];void add(int x,int y){tot_e++;edge[tot_e].u=x;edge[tot_e].v=y;edge[tot_e].next=first[x];first[x]=tot_e;}void dfs(int x){ldfn[x]=++num;size[x]=1;for(int i=first[x];i;i=edge[i].next){int v=edge[i].v;if(v==p[x][0])continue;p[v][0]=x;for(rint i=1;i<=20;++i)p[v][i]=p[p[v][i-1]][i-1];deep[v]=deep[x]+1;dfs(v);size[x]+=size[v];}rdfn[x]=num;}/*void get_fa(){for(rint i=1;i<=n;i++) p[i][0]=fa[i];for(rint i=1;i<=20;i++)for(rint j=1;j<=n;j++)if(p[j][i-1]!=0)p[j][i]=p[p[j][i-1]][i-1];}*/int LCA(int x,int y){if(deep[x]=0;i--)if(k-(1<=0){k-=(1<=0;i--)if(p[x][i]!=0&&p[x][i]!=p[y][i]){x=p[x][i];y=p[y][i];}return p[x][0];}void change(int x,int num,int le,int ri,int &now){if(x==0) return;if(now==0)now=++cnt;qyqyooo[now]+=num;if(le==ri) return;int mid=(le+ri)>>1;if(x<=mid)change(x,num,le,mid,lc[now]);else change(x,num,mid+1,ri,rc[now]);}int search(int lr,int rr,int le,int ri,int now){if(now==0) return 0;if(lr==le&&rr==ri) return qyqyooo[now];int mid=(le+ri)>>1;if(rr<=mid) return search(lr,rr,le,mid,lc[now]);if(lr>mid)return search(lr,rr,mid+1,ri,rc[now]);else return search(lr,mid,le,mid,lc[now])+search(mid+1,rr,mid+1,ri,rc[now]);}int main(){scanf("%d %d",&n,&m);for(rint i=1;i
View Code
【图论专题总结】读者：欸怎么没了？
博主：溜——
T7软件安装：基环树：缩点+树型依赖背包dp
大体思路没什么大问题 。
参数不要写错（不然w10） ， 参数不要写错（不然w50） ， 参数不要写错 ， (不然w70) ， 数组不要开小 ， （不然w80）
（我经历了啥）
#include#include#include#include#include#include#define rint register intusing namespace std;int tot_e,cnt,n,m,w[202],v[202],d[202],dfn[202],low[202];int tot_q,belong[202],qw[202],qv[202],first[202],deg[202];int count[202],list[202],tpt=0,dp[202][505],first2[202],tot_e2;bool instack[202];struct node{int u,v,nxt;}edge[202],edge2[202];struct data{int fa,lc,rc;}tree[202];stack
