P4281 [AHOI2008] 紧急集合 / 聚会

本文主要是介绍P4281 [AHOI2008] 紧急集合 / 聚会，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[AHOI2008] 紧急集合 / 聚会 - 洛谷

树上三个点的路径上找一个点，聚集到一起，经过的边权值和最小

看样例以为是到比较3个点就可以了

写完发现询问2错误了

画图思考

看起来2是最完美的，不会走重复的路线

也可以知道2是3，6的lca，就想把每个lca都做一遍

O(1) dis(x,y)=dep[x]+dep[y]-2*dep[lca(x,y)

ans=dep[x]+dep[y]+dep[z]-2(dep[lca(x,y)]+dep[lca(x,z)+dep[lca(y,z)])

然后能a，就是很复杂的式子

后面发现3个点lca最多就2个

可以化简式子

p=lca(x,y)

ans=dep[x]+dep[y]+dep[z]-dep[p]-2*dep[lca(p,z)]

但是都是要枚举3个lca

于是思考如果存在2个lca是一样的就不应该在那边聚集，如果在那边聚集就会有至少2个人要走重复的路

因此如果有2个lca一样就选不一样的，3个一样就lca(x,y,z)

ans=dep[x]+dep[y]+dep[z]-dep[p]-2*dep[lca(x,y,z)]\

// Problem: P4281 [AHOI2008] 紧急集合 / 聚会
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4281
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=5e5+9;
int a[N];
int n,m;
//树剖
//1.转成线性部分
vector<int> e[N];
void add(int u,int v){e[u].push_back(v);e[v].push_back(u);
}
int fa[N],dep[N],sz[N],wc[N],dis[N];
void dfs1(int u,int f){//fa dep sz wcfa[u]=f;sz[u]=1;dep[u]=dep[f]+1;for(auto & i : e[u]){if(i==f){dis[u]=1;//边权给儿子}if(i!=f){dfs1(i,u);sz[u]+=sz[i];if(sz[i]>sz[wc[u]]){wc[u]=i;}}}
}
int dfn[N],rdfn[N],top[N],vistime;
void dfs2(int u,int Top){//dfn rdfn topdfn[u]=++vistime;a[vistime]=dis[u];//top[u]=Top;if(wc[u]){dfs2(wc[u],Top);for(auto & i : e[u]){if(i!=wc[u] && i!=fa[u]){dfs2(i,i);}}}
}
int lca(int u,int v){while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]){swap(u,v);}u=fa[top[u]];}return dep[u]>dep[v]?v:u;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n-1;i++){int a,b;cin>>a>>b;add(a,b);}dfs1(1,0);dfs2(1,1);// t.build(1,1,n);for(int i=1;i<=m;i++){int x,y,z;cin>>x>>y>>z;int p1=lca(x,y),p2=lca(x,z),p3=lca(y,z);int p=0;int P=lca(p1,p2);if(p1==p2){p=p3;// cout<<p3<<" "<<(dep[x]+dep[y]+dep[z]-dep[p3]-2*dep[lca(p3,p1)])<<'\n';// continue;}if(p2==p3){p=p1;// cout<<p1<<" "<<(dep[x]+dep[y]+dep[z]-dep[p1]-2*dep[lca(p3,p1)])<<'\n';// continue;}if(p1==p3){p=p2;// cout<<p2<<" "<<(dep[x]+dep[y]+dep[z]-dep[p2]-2*dep[lca(p2,p1)])<<'\n';}//dis(x,y)=dep[x]+dep[y]-2*dep[lca(x,y)]cout<<p<<" "<<(dep[x]+dep[y]+dep[z]-dep[p]-2*dep[P])<<'\n';}return 0;
}

这篇关于P4281 [AHOI2008] 紧急集合 / 聚会的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---