![[树的基础概念.png]]
树的遍历
二叉树遍历分类
DFS前序遍历
根节点-左儿子-右儿子
DFS中序遍历
左儿子-根节点-右儿子
DFS后序遍历
左儿子-右儿子-根节点
BFS层序遍历![[树的遍历.png]]
代码:
#include <bits/stdc++.h>using namespace std;
const int N=20;
int n,lc[N],rc[N];//每个节点的左右儿子//前序遍历:根节点-左儿子-右儿子
void dfs1(int i){cout<<i<<" ";if(lc[i]) dfs1(lc[i]);if(rc[i]) dfs1(rc[i]);
} //中序遍历:左儿子-根节点-右儿子
void dfs2(int i){if(lc[i]) dfs2(lc[i]);cout<<i<<" ";if(rc[i]) dfs2(rc[i]);
} //后序遍历:左儿子-右儿子-根节点
void dfs3(int i){if(lc[i]) dfs3(lc[i]);if(rc[i]) dfs3(rc[i]);cout<<i<<" ";
} //bfs层序遍历
void bfs(int i){queue<int> q;q.emplace(1);while(!q.empty()){cout<<q.front()<<" ";if(lc[q.front()]) q.emplace(lc[q.front()]);if(rc[q.front()]) q.emplace(rc[q.front()]);q.pop();}
} int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>lc[i]>>rc[i];/*102 34 56 78 00 90 010 00 00 00 0*/dfs1(1);cout<<"\n";dfs2(1);cout<<"\n";dfs3(1);cout<<"\n";bfs(1);cout<<"\n";return 0;/*1 2 4 8 5 9 3 6 7 108 4 2 5 9 1 6 3 10 78 4 9 5 2 6 10 7 3 11 2 3 4 5 6 7 8 9 10*/
}
树的直径和重心
树的直径![[树的直径.png]]
根据两个节点必然存在一个点作为最深的叶子节点，则可以先跑以便DFS找到这个最深的叶子节点(取一个即可)，然后再以该节点为根节点再跑一遍DFS寻找此时的最深的叶子节点(取一个即可)，树的直径就是路径的长度,两遍DFS求得树的直径,三遍DFS求得直径两个端点各自到任意节点的深度
结论:
对于树上任意一个点，距离它最远的点一定是直径的某一个端点。
3029卖树
1.题目树的价值被定义为根节点到所有节点的路径长度的最大值，由上述结论可知寻找到直径的两个端点u,v,然后暴力遍历所有节点，得到价值减去代价即可
代码(重点学习):
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=2e5+10;
//以1为根节点每个节点的节点深度和父节点，以及换根后每个节点的节点深度和父节点
ll dep1[N],depU[N],depV[N];
int t;
//二维数组，记录每个节点的儿子,即边
vector<int> g[N]; //dfs搜索,参数:x-当前节点,f:父节点,dep[]:深度数组,fa[]:父节点数组
void dfs(int x, int f, ll dep[]){//更新dep和fadep[x]=dep[f]+1; fa[x]=f;//遍历x的儿子for(auto &y:g[x]){//跳过fif(y==f) continue;//继续dfsdfs(y,x,dep,fa); }
} int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>t;while(t--){ll n,k,c;cin>>n>>k>>c;//初始化 for(int i=1;i<=n;i++){dep1[i]=depU[i]=0;g[i].clear();}for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;//存储边,即存储儿子 g[u].emplace_back(v);g[v].emplace_back(u); }//开始第一遍dfs遍历，更新dep1数组//根节点dep1[1]=0,所以令dep1[0]=-1 dep1[0]=-1;dfs(1,0,dep1);//寻找最深的点u int u=0;for(int i=1;i<=n;i++){if(dep1[i]>dep1[u]) u=i;} //再以u为根节点DFS一遍更新depUdepU[0]=-1;dfs(u,0,depU);//寻找最深的点vint v=0;for(int i=1;i<=n;i++){if(depU[i]>depU[v]) v=i;} //再以v为根节点DFS一遍更新depVdepV[0]=-1;dfs(v,0,depV);//遍历所有节点ll ans=0;for(int i=1;i<=n;i++){//depU[i],depV[i],dep1[i]分别为u,v,1到第i个节点的路径个数，乘以权值即为价值,乘以c即为代价 ans=max(ans,max(depU[i],depV[i])*k-dep1[i]*c);} cout<<ans<<endl;}return 0;
}
2013大臣的旅费
学习:
1.类似于树的直径从1号结点DFS遍历找到离1号结点最远的结点作为根节点进行换根，然后再以换完的根节点开始DFS找到最终答案
代码:
#include <bits/stdc++.h>using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=1e5+10;//邻接表
vector<PII> g[N];
int n;
ll sum[N];//记录root结点到第i个结点的最大长度
ll maxSum=0; void dfs(int cur,int f,int tsum){//遍历儿子for(const auto &y:g[cur]){if(y.first==f) continue;dfs(y.first,cur,tsum+y.second);} sum[cur]=tsum;maxSum=max(sum[cur],maxSum);
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n-1;i++){int p,q,d;cin>>p>>q>>d;g[p].emplace_back(q,d);g[q].emplace_back(p,d);}//换根 dfs(1,0,0); int root=0;for(int i=1;i<=n;i++){if(sum[i]==maxSum){root=i;break; }} //dfs找最大值maxSum=0;for(int i=1;i<=n;i++) sum[i]=0;dfs(root,0,0); cout<<(1+maxSum)*maxSum/2+10*maxSum;return 0;
}
树的重心![[树的重心.png]]
树的重心:删除某个节点，使得剩余联通块(子树)的大小的最大值最小
mss[x]表示x节点所有子树大小的最大值
性质:
(最关键)1.为重心的节点的所有子树的大小一点<=n/2(如上面的mss[1,2]=4<=8/2),除了重心以外的其他节点,都必然存在一个子树>n/2(如上图mss[3,4,5,6,7,8]>8/2)
2.一颗树至多有2个重心，如果存在两个重心，则必然相邻，如上图的1和2
3.树中所有点到某个点的距离和中，到重心的距离和是最小的(2个重心相等都最小)
![[树的重心2.png]]
利用性质1求树的重心:
//sz[i]是以i为根节点的子树的大小,mss[i]即上面的删去x节点所有子树大小的最大值
void dfs(int x,int fa){sz[x]=1,mss[x]=0;//遍历儿子for(auto &y:g[x]){if(t==fa) continue;dfs(y,x);//从下向上更新szsz[x]+=sz[y];//yi一侧的子树mss[x]=max(mss[x],sz[y]);}//还有1个子树mss[x]=max(mss[x],n-sz[x]);//是重心if(mss[x]<=n/2) v.emplace_back(x);
}
6179奇特树的重心
学习:
1.模版题，开始遍历是dfs(1,-1)
代码:
#include <bits/stdc++.h>using namespace std;
const int N=1e5+10;
vector<int> g[N]; //路径
int n,mss[N],sz[N],ans; //mss[i]为删除第i个结点最大的剩余联通块点数,sz[i]为以i为根节点的子树的大小 //第x个结点,第x个结点的父结点
void dfs(int x,int f){sz[x]=1,mss[x]=0;//遍历儿子for(auto &y:g[x]){if(y==f) continue;dfs(y,x);sz[x]+=sz[y];mss[x]=max(mss[x],sz[y]);} //剩余的一颗子树mss[x]=max(mss[x],n-sz[x]);//是重心if(mss[x]<=n/2) ans=x;
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;g[u].emplace_back(v);g[v].emplace_back(u);}dfs(1,0);cout<<mss[ans];return 0;
}
4354举办聚会
学习:
1.正常的邻接表储存边的两个结点，一个数组储存每个结点的人数，再求和获取总人数大小
2.因为要求所有结点到某个结点的路径之和的第k小的，所有要一个数组dp储存所有结点到某个结点的路径和，然后自定义排序获取第k小的结点
3.要获得所有结点到某个结点的路径和，就是移动父结点到子结点，子结点的子树路径都-1，而另一部分全部+1，这个DFS2的逻辑
4.要获得子树的人数和sz，得首先一个DFS1遍历获取，且要获得dp[1]的大小，得知道每个结点到1结点的深度dep,所有DFS1完成dep和sz两个数组的更新
综上，DFS1更新dep数组和sz数组，是上面重心的逻辑，DFS2换根更新dp数组，是这题新的逻辑
代码:
#include <bits/stdc++.h>using namespace std;
const int N=1e4+10;
typedef long long ll;int n,k;
//g为邻接表
vector<ll> g[N];
//a[i]:i结点对应的人数
//dep[i]:i结点到1结点的深度,dep[1]=0
//sz[i]:以i结点为根结点的子树的人数和,sum-sz[i]为令一个子树人数和
//dp[i]:所有结点到i结点的路径和
ll a[N],dep[N],sz[N],sum,dp[N];//第一次dfs,更新dep和sz
void dfs1(int x,int fa){sz[x]=a[x];dep[x]=dep[fa]+1;//遍历儿子for(auto &y:g[x]){if(y==fa) continue;dfs1(y,x);sz[x]+=sz[y];}
}//第一次dfs,更新dp
void dfs2(int x,int fa){//遍历儿子for(auto &y:g[x]){if(y==fa) continue;//更新dp[y],根节点从x移动到y,y的子树路径全部减1，另一部分全部加1dp[y]=dp[x]-sz[y]*1+(sum-sz[y])*1;dfs2(y,x); }
}bool cmp(int &x,int &y){//优先取人数和最小的 if(dp[x]!=dp[y]) return dp[x]<dp[y];//相等则取节点编号小的return x<y;
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;g[u].emplace_back(v);g[v].emplace_back(u);}//第一次dfs,更新dep和szdep[0]=-1;dfs1(1,0); //获得dp[1]for(int i=2;i<=n;i++){dp[1]+=dep[i]*a[i];} //第二次dfs,更新dpdfs2(1,0); //自定义排序,给dp数组排序vector<int> ans;for(int i=1;i<=n;i++) ans.emplace_back(i);sort(ans.begin(),ans.end(),cmp);//输出第k小的cout<<ans[k-1]; return 0;
}
综上,dfs能获取树的深度数组dep,和子树数组sz
LCA
树上的路径问题想到lca
LCA最近公共祖先
指有根树中，找出某两个结点x和y最近的公共祖先
![[LCA.jpg]]
倍增法求LCA
1.本质是dp,以及任何数都能被2进制表示
2.首先需要dfs获得dep数组和fa数组
fa[x][i]表示第x个结点向上2^i次方到达的结点
所以有fa[x][i]=fa[fa[x][i-1]][i-1],迭代更新，表示跳2^i次方，先跳2^(i-1)次方，再跳2^(i-1)次方
代码:
void dfs(int x,int f){//更新depdep[x]=dep[f]+1;//初始化fa[x][0]fa[x][0]=f;//更新fa,因为是从上向下更新的，所以fa[祖先][i-1]肯定存在for(int i=1;i<=20;i++){ //基本上不会超过2^20fa[x][i]=fa[fa[x][i-1]][i-1];}//遍历儿子for(auto &y:g[x]){if(y==f) continue;dfs(y,x);}
}
3.求LCA(x,y)
(1)假设x深度更深,通过fa数组从大到小让x先往上跳，遍历,保证dep[x]<=dep[y]
(2)此时x==y或者dep[x]=dep[y],然后从大到小让x和y一起跳，保证fa[x][i]!=fa[y][i],最后LCA(x,y)=fa[x][0]
理解:让x和y先到达同一深度
理解:这里保证fa[x][i]!=fa[y][i],因为跳是从大到小跳，害怕先跳大的找到更上层的公共祖先，但不是最近的，所以先找到最近祖先的下一层，最终答案再跳一次即可
代码:
int lca(int x,int y){//假设x深度大if(dep[y]>dep[x]) swap(x,y);//从大到小跳x，保证dep[x]<=dep[y]for(int i=20;i>=0;i--){//x跳了dep不会大于dep[y]if(dep[fa[x][i]]<=dep[y]){x=fa[x][i];}}//x==y,直接找到if(x==y) return x;//dep[x]=dep[y]//从大到小跳x和y，保证fa[x][i]!=fa[y][i]for(int i=20;i>=0;i--){//x,y跳了fa[x][i]!=fa[y][i]if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}}//答案为fa[x][0]return fa[x][0];
}
4385最近公共祖先LCA查询
学习:
1.模版题
代码:
#include <bits/stdc++.h>using namespace std;
const int N=1e5+10;
//邻接表
vector<int> g[N];
//dep数组和fa数组
int dep[N],fa[N][21];
int n,q; //dfs
void dfs(int x,int f){//更新dep dep[x]=dep[f]+1;//初始化fa[x][0] fa[x][0]=f;//更新fa for(int i=1;i<=20;i++){fa[x][i]=fa[fa[x][i-1]][i-1];}//遍历儿子 for(auto &y:g[x]){if(y==f) continue;dfs(y,x);}
}//lca
int lca(int x,int y){//x更深 if(dep[x]<dep[y]) swap(x,y);//先让x和y同一深度，保证dep[x]>=dep[y]for(int i=20;i>=0;i--){if(dep[fa[x][i]]>=dep[y]){x=fa[x][i];}} //x=yif(x==y) return x;//dep[x]=dep[y]//同时上移x和y，保证fa[x][i]!=fa[y][i]for(int i=19;i>=0;i--){if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}} //返回答案return fa[x][0];
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;g[u].emplace_back(v);g[v].emplace_back(u);}//更新dep和fadep[0]=-1;dfs(1,0); //LCAcin>>q;while(q--){int a,b;cin>>a>>b;cout<<lca(a,b)<<endl;}return 0;
}