Codeforces 832D: Misha, Grisha and Underground 【LCA模板】
2024-09-05 22:50:22
模板copy from http://codeforces.com/contest/832/submission/28835143
题意,给出一棵有n个结点的树,再给出其中的三个结点 s,t,f ,求路径 (s,t) (s,f) (t,f) 三者的最大公共结点数
对于(t,f) (s,f)的公共结点数,有
懒得细想了,暴力对s,t,f生成排列(反正一共仨数,最多也就3!=6个排列),求各种情况下的最大ans
#include<bits/stdc++.h>
using namespace std; const int N=1e5+;
const int DEG=;
//int time_tag,in[N],out[N],dep[N];
int dep[N];
int fa[N][DEG];
int n,q;
vector<int> e[N]; void dfs(int u)
{
// in[u]=++time_tag;
for(int i=;i<DEG;i++)
fa[u][i]=fa[fa[u][i-]][i-];
for(int i=;i<e[u].size();i++)
{
int v=e[u][i];
dep[v]=dep[u]+;
fa[v][]=u;
dfs(v);
}
// out[u]=time_tag;
} int lca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
for(int i=,d=dep[u]-dep[v];d;i++,d>>=)
if(d&) u=fa[u][i];
if(u==v) return u;
for(int i=DEG-;i>=;i--)
if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][];
} int dis(int u,int v)
{
return dep[u]+dep[v]-*dep[lca(u,v)];
} int main()
{
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++)
{
int p;
scanf("%d",&p);
e[p].push_back(i);
}
dfs();
while(q--)
{
int k[];
for(int i=;i<;i++) scanf("%d",&k[i]);
sort(k,k+);
int ans=;
do
{
ans=max(ans,(dis(k[],k[])+dis(k[],k[])-dis(k[],k[]))/);
}while(next_permutation(k,k+));
printf("%d\n",ans+);
}
}
//当时其实想到了ans的表达式,但是不会LCA,不自信是否把题读准确了(前边读题出的问题很大。。),所以直接放弃了这道题。。然而事后发现这题没读错,算法也没错。。。如果直接从网上copy一份求树上两点距离的板子,这题还是可以过的——一只弱鸡的懊悔
最新文章
- EF架构~在Linq to Entity中使用日期函數
- POJ1037A decorative fence(动态规划+排序计数+好题)
- swift:入门知识之类和对象
- Arduino 电平转换 升压 OUTPUT与9V/12V元件通信
- LeetCode_Valid Palindrome
- Hdu1384-Intervals(差分约束)
- redis memcache
- jenkins 从git拉取代码
- vm Linux centos 链接外网
- python --- 03 整型 bool 字符串 for循环
- Linux MySQL 4G内存my.cnf配置表(转)
- SQL优化|Java面试题
- npm WARN react-native-maps@0.14.0 requires a peer of react@>;=15.4.0 but none was installed
- C# BBcode 转 Markdown
- C/C++——赋值理解(匿名临时对象)
- poj 2337(单向欧拉路的判断以及输出)
- PAT 1130 Infix Expression[难][dfs]
- 字符串的最小最大表示法O(n)
- OpenCV代码提取:dft函数的实现
- redis之(二十)redis的总结一