本文主要是介绍树章节习题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今天也是小小的把树的章节的内容大体过了一遍，总共有树上dp，LCA（最近公共祖先），树的直径，以及树上差分
P1395 会议
很经典的树上dp里面的换根dp问题，现在这里说几个数组
sz数组，用于统计以1为节点，每个节点的子树大小
sum数组，用于统计每个子树上总节点的累加
f 数组，用于统计以每个点为根的时候的路径长度
我们通过画图分析可知，换根公式为 f [ v ] = f [ u ] - sz [ u ] + ( n - sz [ u ])
我们就可以完成这个题目了
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int u,v;
vector<int> e[50005];
int sz[50005];
int sum[50005];
int f[50005];void dfs1(int v,int fa)
{sz[v]=1;for(int u:e[v]){if(u!=fa){dfs1(u,v);sz[v]+=sz[u];}}
}void get(int v,int fa)
{sum[v]=0;for(int u:e[v]){if(u!=fa){get(u,v);sum[v]+=sz[u]+sum[u];}}
}void dfs2(int v,int fa)
{for(int u:e[v]){if(u!=fa){f[u]=f[v]-sz[u]+(n-sz[u]);dfs2(u,v);}}
}
signed main()
{cin>>n;for(int i=1;i<n;i++){cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}dfs1(1,0);get(1,0);f[1]=sum[1];dfs2(1,0);int maxn=0x3f3f3f3f,flag=0;for(int i=1;i<=n;i++){if(f[i]<maxn){flag=i;maxn=f[i];}}cout<<flag<<" "<<maxn;return 0;
} P3128 [USACO15DEC] Max Flow P
这道题乍一看，我没看出来哪里有最近公共祖先的思想，但是，后面在纸上写写画画的时候，发现 这其实就是最近公共祖先+树上差分
我们每次要在树上对每次提问的路径进行修改，那么我们这个是点修改，因此我们需要将经过的两个点的差分数组dif++，最近公共祖先和其父节点dif--
然后就直接出来了
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int u,v;
vector<int> e[50005];
int dep[50005];
int f[50005][17];
int dif[50005];
int ans;
void dfs(int v,int fa)
{dep[v]=dep[fa]+1;f[v][0]=fa;for(int i=1;i<17;i++){f[v][i]=f[f[v][i-1]][i-1];}for(int u:e[v]){if(u!=fa){dfs(u,v);}}
}
int lca(int u,int v)
{if(dep[u]<dep[v]){swap(u,v);}for(int i=17-1;i>=0;i--){if(dep[f[u][i]]>=dep[v])u=f[u][i];}if(u==v)return v;for(int i=16;i>=0;i--){if(f[u][i]!=f[v][i]){u=f[u][i];v=f[v][i];}}return f[u][0];
}
void sign_up(int v,int fa)
{for(int u:e[v]){if(u!=fa){sign_up(u,v);dif[v]+=dif[u];}}ans=max(ans,dif[v]);
}
signed main()
{cin>>n>>k;for(int i=1;i<n;i++){cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}dfs(1,0);for(int i=1;i<=k;i++){cin>>u>>v;dif[u]++;dif[v]++;dif[lca(u,v)]--;dif[f[lca(u,v)][0]]--;}sign_up(1,0);cout<<ans;return 0;
}P3398 仓鼠找 sugar
归根到底，其实还是最近公共祖先的思想，但是我们这道题要想清楚的是，我们如何判断有两条路径相交，一方面是如果两条路径相交，那么第一条路径的公共祖先一定会在第二条路径上，但是我们如何去判断一个点在一个路径上，因此我们需要用到深度数组，如果其公共祖先在a，b这条路径上，那么a~公共祖先的距离+b~公共祖先的距离=a~b的距离
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
int u,v;
vector<int> e[100005];
int dep[100005];
int f[100005][18];
void dfs(int v,int fa)
{dep[v]=dep[fa]+1;f[v][0]=fa;for(int i=1;i<18;i++){f[v][i]=f[f[v][i-1]][i-1];}for(int u:e[v]){if(u!=fa){dfs(u,v);}}
}
int lca(int u,int v)
{if(dep[u]<dep[v])swap(u,v);for(int i=17;i>=0;i--){if(dep[f[u][i]]>=dep[v])u=f[u][i];}if(u==v)return v;for(int i=17;i>=0;i--){if(f[u][i]!=f[v][i]){u=f[u][i];v=f[v][i];}}return f[u][0];
}
int dis(int u,int v)
{int LCA=lca(u,v);return abs(dep[u]-dep[LCA])+abs(dep[LCA]-dep[v]);
}
signed main()
{cin>>n>>q;for(int i=1;i<n;i++){cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}dfs(1,0);int a,b,c,d;for(int i=1;i<=q;i++){cin>>a>>b>>c>>d;int x=lca(a,b),y=lca(c,d);if((dis(a,y)+dis(b,y)==dis(a,b))||(dis(c,x)+dis(d,x)==dis(c,d)))cout<<"Y\n";elsecout<<"N\n";}return 0;
}这篇关于树章节习题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
