题目传送门

LCA,对于每一个(x,y,z),两两求LCA得最优解或求出LCA不同于其他两组的那个为最优解。

code:

/**************************************************************
    Problem: 1787
    User: yekehe
    Language: C++
    Result: Accepted
    Time:5212 ms
    Memory:51604 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
int read()
{
    char c;while(c=getchar(),c<''||c>'');
    int x=c-'';while(c=getchar(),c>=''&&c<='')x=(x<<)+(x<<)+c-'';
    return x;
}
 
const int MAXN=;
int N,M;
int head[MAXN],to[MAXN<<],nxt[MAXN<<],cnt;
void add(int x,int y)
{
    to[cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
    cnt++;
}
 
int D[MAXN];
int f[][MAXN];
void dfs(int now,int deep,int fa)
{
    D[now]=deep;
    f[][now]=fa;
        for(int i=head[now];i!=-;i=nxt[i])
            if(!D[to[i]])
                dfs(to[i],deep+,now);
    return ;
}
int Me;
int get(int x,int y)
{
    if(D[x]<D[y])swap(x,y);
    for(int i=;i>=;i--)
        if(D[f[i][x]]>=D[y])x=f[i][x];
    if(x==y)return x;
    for(int i=;i>=;i--)
        if(f[i][x]!=f[i][y])
            x=f[i][x],y=f[i][y];
    return f[][x];
}
 
int solve(int x,int y)
{
    return D[x]+D[y]-(D[get(x,y)]<<);
}
int main(){
    memset(head,-,sizeof head);
    memset(nxt,-,sizeof nxt);
    N=read(),M=read();
    register int i,j;
        for(i=;i<N;i++){
            int x=read(),y=read();
            add(x,y),add(y,x);
        }
    dfs(,,);
        for(i=;i<=;i++)
            for(j=;j<=N;j++)
                f[i][j]=f[i-][f[i-][j]];
        for(i=;i<=M;i++){
            int x=read(),y=read(),z=read();
            int a=get(x,y),b=get(y,z),c=get(x,z);
            int dist=;
            if(a==b)dist=c;else
            if(b==c)dist=a;else
            dist=b;
            printf("%d %d\n",dist,solve(x,dist)+solve(y,dist)+solve(z,dist));
        }
    return ;
}

最新文章

  1. Android随笔之——PackageManager详解
  2. 【类库】容器对象(List、DataTable、 DataView、Dictionary)
  3. 读书笔记:javascript高级技巧(二)
  4. redis主从遇到的两个坑
  5. tomcat 禁止某些文件(夹)的访问
  6. 【翻译】Ext JS最新技巧——2014-5-12
  7. win7+ubuntu 13.04双系统安装方法
  8. Observer设计模式【利用商品概念解释】
  9. JavaScript动态更改页面元素
  10. 3D图片变换
  11. 微信小程序开发《二》:http请求的session管理
  12. 【流量】netflow 基础知识
  13. Python开发之路
  14. [国嵌攻略][119][Linux中断处理程序设计]
  15. 设置修改CentOS系统时区
  16. ng-select 下拉的两种方式
  17. python设计模式浅析
  18. MySQL 把两个结果集拼接到一起(两个结果集的列一模一样)
  19. 微信小程序实际开发中学习
  20. bzoj 1222

热门文章

  1. C#中的三种timer
  2. Vue2学习笔记:class和style
  3. Ajax 请求下载 Execl 文件
  4. include方便查找
  5. Replace-iOS
  6. swift知识点 [1]
  7. Custom Settings.ini 和 bootstrap.ini 配置
  8. 铁乐学python_day01-作业
  9. (1)String类 (2)StringBuilder类和StringBuffer类 (3)日期相关的类
  10. 转载】JQuery中如何传递参数如click(),change()等具体实现