xp04 - day06
2025-08-17 16:57:24
发布于：浙江
163阅读
0回复
0点赞
树的创建 和 遍历
#include<bits/stdc++.h>
using namespace std;
vector<int> tr[100010];
void dfs(int u,int fa){
// for(int i=0;i<tr[u].size();i++){
// int son = tr[u][i];
// if(son==fa)continue;
// }
for(int son:tr[u]){
if(son==fa)continue;
dfs(son,u);
}
}
int main(){
int n,q,root;
cin>>n>>q>>root;
for(int i=1;i<=n-1;i++){
int a,b;
cin>>a>>b;
tr[a].push_back(b);
tr[b].push_back(a);
}
dfs(root,-1);
return 0;
}
lca 暴力版本
#include<bits/stdc++.h>
using namespace std;
vector<int> tr[500001];
int dep[500001],fa[500001];
// dep[son] = dp[u]+1
// fa[son] = u
void dfs(int u,int f){
for(int son:tr[u]){
if(son==f)continue;
dep[son] = dep[u] + 1;
fa[son] = u;
dfs(son,u);
}
}
int lca(int x,int y){
// 默认x的高度要>y
if(dep[x]<dep[y])swap(x,y);
// 将x和y在同一高度上
while(dep[x]!=dep[y]){
x = fa[x];
}
if(x==y)return x;//考虑在同一个树枝上
while(x!=y){
x=fa[x];
y=fa[y];
}
return x;
}
int main(){
int n,q,root;
cin>>n>>q>>root;
for(int i=1;i<=n-1;i++){
int a,b;
cin>>a>>b;
tr[a].push_back(b);
tr[b].push_back(a);
}
dfs(root,-1);//预处理 dad 和 depth
while(q--){
int x,y;
cin>>x>>y;
cout<<lca(x,y)<<endl;
}
return 0;
}
LCA 优化版
#include<bits/stdc++.h>
using namespace std;
vector<int> tr[500001];
int dep[500001],fa[500001][21];
void dfs(int u,int f){
fa[u][0] = f;//u往上跳一格的父亲是f
for(int i=1;i<=20;i++)fa[u][i] = fa[fa[u][i-1]][i-1];//预处理lca
for(int son:tr[u]){
if(son==f)continue;
dep[son] = dep[u] + 1;
dfs(son,u);
}
}
int lca(int x,int y){
// 默认x的高度要>y
if(dep[x]<dep[y])swap(x,y);
// 将x和y在同一高度上
for(int i=20;i>=0;i--){
if(dep[fa[x][i]]>=dep[y]){
x=fa[x][i];
}
}
//cout<<x<<" "<<y<<endl;
if(x==y)return x;//考虑在同一个树枝上
for(int i=20;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
int main(){
int n,q,root;
cin>>n>>q>>root;
for(int i=1;i<=n-1;i++){
int a,b;
cin>>a>>b;
tr[a].push_back(b);
tr[b].push_back(a);
}
dep[root] = 1;
dfs(root,0);//预处理 dad 和 depth
while(q--){
int x,y;
cin>>x>>y;
cout<<lca(x,y)<<endl;
}
return 0;
}
⼤量的⼯作沟通
#include<bits/stdc++.h>
using namespace std;
const int N = 500010,M = 20;
vector<int> tr[N];
int fa[N][M];
int dep[N];
void dfs(int u,int p){
fa[u][0]=p;
for(int i=1;i<M;i++){
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int son:tr[u]){
dep[son] = dep[u] + 1;
dfs(son, u);
}
}
int lca(int x,int y){
// x高度<y高度 swap
if(dep[x]<dep[y]) swap(x,y);
// 让x和y高度相同
for(int i=M-1;i>=0;i--){
if(dep[fa[x][i]]>=dep[y]){
x=fa[x][i];
}
}
// 特判 x=y的情况
if(x==y) return x;
for(int j=M-1;j>=0;j--){
if(fa[x][j]!=fa[y][j]){
x=fa[x][j];
y=fa[y][j];
}
}
return fa[x][0];
}
int main(){
int n;
cin>>n;
for(int i=2;i<=n;i++){
int p;
scanf("%d",&p);
p++;
tr[p].push_back(i);
}
dep[1] = 1;
dfs(1, 0);
int m;
cin>>m;
while(m--){
int k;
cin>>k;
int ans = 0;
for(int i=1;i<=k;i++){
int x;
cin>>x;
x++;
if(ans==0)ans = x;
else {
ans = lca(ans,x);
}
}
cout<<ans-1<<endl;
}
return 0;
}
树上差分
树的直径 动态规划
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, ans;
vector<int> g[N];
int dfs(int u, int fa) {
int d1 = 0, d2 = 0;
for (int v : g[u]) {
if (v == fa) continue;
int d = dfs(v, u) + 1;
if (d >= d1) {
d2 = d1;
d1 = d;
} else if (d > d2) {
d2 = d;
}
}
ans = max(ans, d1 + d2);
return d1;
}
int main() {
cin >> n;
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1, -1);
cout << ans << endl;
return 0;
}
树的直径 2次dfs
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
vector<int> g[N];
int id; // 记录最远点
int max_dist; // 记录最远距离
void dfs(int u, int fa, int dist) {
if (dist > max_dist) {
max_dist = dist;
id = u;
}
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u, dist + 1);
}
}
int main() {
cin >> n;
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
// 第一次 DFS，从 1 出发，找到最远点 p1
max_dist = -1;
dfs(1, -1, 0);
int p1 = id;
// 第二次 DFS，从 p1 出发，找到最远点 p2
max_dist = -1;
dfs(p1, -1, 0);
int ans = max_dist;
cout << ans << endl;
return 0;
}
换根dp
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n;
vector<int> tr[N];
long long size[N],dp[N],ans,id;
void dfs(int u, int fa) {
size[u] = 1;
for(int son:tr[u]){
if(son==fa)continue;
dfs(son,u);
dp[u] += dp[son] + size[son];
size[u] += size[son];
}
}
void dfs1(int u, int fa) {
for(int son:tr[u]){
if(son==fa)continue;
long long p = (dp[u]-dp[son]-size[son])+size[u]-size[son];
long long s = size[son];
dp[son]+=p;
size[son] = size[u];
if(ans<dp[son]){
ans=dp[son];
id = son;
}
dfs1(son,u);
dp[son]-=p;
size[son] = s;
}
}
int main() {
cin >> n;
for (int i = 1; i <= n - 1; i++) {
int a, b;
cin >> a >> b;
tr[a].push_back(b);
tr[b].push_back(a);
}
dfs(1, -1);
ans = dp[1];
id = 1;
dfs1(1,-1);
cout << id << endl;
return 0;
}
割裂 树上差分做法
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010,M = 23;
vector<int> tr[N];
int fa[N][M];
long long dep[N],a[N],ans = 0;
void dfs(int u,int p){
fa[u][0] = p;
for(int i=1;i<=M-1;i++){
fa[u][i] = fa[fa[u][i-1]][i-1];
}
for(int son:tr[u]){
if(son == p) continue;
dep[son] = dep[u] + 1;
dfs(son, u);
}
}
int lca(int x,int y){
if(dep[x] < dep[y]) swap(x,y);
for(int i=M-1;i>=0;i--){
if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
}
if(x == y) return x;
for(int i=M-1;i>=0;i--){
if(fa[x][i] != fa[y][i]){
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
void dfs1(int u,int p){
for(int son:tr[u]){
if(son==p)continue;
dfs1(son,u);
a[u]+=a[son];
}
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n-1;i++){
int a,b;
scanf("%d%d",&a,&b);
tr[a].push_back(b);
tr[b].push_back(a);
}
dep[1] = 1;
dfs(1, 0);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
int p = lca(x,y);
a[x]--;
a[y]--;
a[p]++;
a[fa[p][0]]++;
//好的我就减去
}
int x,y;
scanf("%d%d",&x,&y);
//将不行的去掉
int ans = 0;
int p =lca(x,y);
dfs1(1,0);
while(x!=p){
if(a[x]==0)ans++;
x=fa[x][0];
}
while(y!=p){
if(a[y]==0)ans++;
y=fa[y][0];
}
if(a[p]==0)ans++;
cout<<ans;
return 0;
}
有帮助，赞一个