题目链接

模板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一份求树上两点距离的板子,这题还是可以过的——一只弱鸡的懊悔

最新文章

  1. EF架构~在Linq to Entity中使用日期函數
  2. POJ1037A decorative fence(动态规划+排序计数+好题)
  3. swift:入门知识之类和对象
  4. Arduino 电平转换 升压 OUTPUT与9V/12V元件通信
  5. LeetCode_Valid Palindrome
  6. Hdu1384-Intervals(差分约束)
  7. redis memcache
  8. jenkins 从git拉取代码
  9. vm Linux centos 链接外网
  10. python --- 03 整型 bool 字符串 for循环
  11. Linux MySQL 4G内存my.cnf配置表(转)
  12. SQL优化|Java面试题
  13. npm WARN react-native-maps@0.14.0 requires a peer of react@&gt;=15.4.0 but none was installed
  14. C# BBcode 转 Markdown
  15. C/C++——赋值理解(匿名临时对象)
  16. poj 2337(单向欧拉路的判断以及输出)
  17. PAT 1130 Infix Expression[难][dfs]
  18. 字符串的最小最大表示法O(n)
  19. OpenCV代码提取:dft函数的实现
  20. redis之(二十)redis的总结一

热门文章

  1. jmeter之关联操作
  2. 【openstf】自己的云测平台——mac安装openstf
  3. day17跨文件夹导入模块,模块的两种被执行方式,包,直接使用包中模块,包的管理
  4. linux(centos7.0以上)下对mysql数据库的导入导出
  5. 应用安全-Web安全-子域名/相关域名
  6. pandas 入门(3)
  7. python基础-9.2 单例模式
  8. pytony格式化输出-占位符
  9. Java初始化块及执行顺序
  10. 极*Java速成教程 - (3)