bzoj 1818/1732 聚会

news/2024/11/16 6:28:58/
首先,答案的点一定在三组lca中的一个上
它在那个最深的lca上,不要问我为什么
或者,这三组lca一定有两个重复的,答案是那个不重复的。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>

#define ll long long
#define inf 1e9
#define eps 1e-10
#define md
#define N 500010
using namespace std;
struct yts { int t,ne;} e[2*N];
int fa[N][22],dep[N],v[N];
bool vis[N];
int n,num=0;
void put(int x,int y)
{
num++; e[num].t=y;
e[num].ne=v[x]; v[x]=num;
}
void dfs(int x)
{
vis[x]=1;
for (int i=v[x];i;i=e[i].ne)
{
int y=e[i].t;
if (!vis[y])
{
fa[y][0]=x; dep[y]=dep[x]+1;
dfs(y);
}
}
}

void build_lca()
{
for (int j=1;j<=20;j++)
for (int i=1;i<=n;i++)
if (fa[i][j-1]) fa[i][j]=fa[fa[i][j-1]][j-1];
}

int lca(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y);
int t=dep[x]-dep[y];
for (int i=20;i>=0;i--) if (t&(1<<i)) x=fa[x][i];
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 dist(int x,int y)
{
int z=lca(x,y);
return (dep[x]-dep[z])+(dep[y]-dep[z]);
}

int main()
{
int m;
scanf("%d%d",&n,&m);
for (int i=1;i<=n-1;i++)
{
int x,y;
scanf("%d%d",&x,&y);
put(x,y); put(y,x);
}
dep[1]=1; dfs(1);
build_lca();
for (int i=1;i<=m;i++)
{
int x,y,z,ans;
scanf("%d%d%d",&x,&y,&z);
int a=lca(x,y),b=lca(y,z),c=lca(x,z);
ans=a;
if (dep[b]>dep[ans]) ans=b;
if (dep[c]>dep[ans]) ans=c;
printf("%d %d\n",ans,dist(x,ans)+dist(y,ans)+dist(z,ans));
}
return 0;
}


http://www.ppmy.cn/news/244202.html

相关文章

Yolov5 (v6.1)添加注意力机制

Apply Transformer in the backbone 1、要把注意力结构代码放到common.py文件中 2、手把手带你Yolov5 (v6.1)添加注意力机制(一)&#xff08;并附上30多种顶会Attention原理图&#xff09; 3、手把手带你Yolov5 (v6.1)添加注意力机制(二)&#xff08;在C3模块中加入注意力机…

最新万能门店小程序V5.1.0 独立版源码

使用说明&#xff08;更详细配置见程序根目录下的pdf文档&#xff09;&#xff1a; 1&#xff0c;宝塔新建网站&#xff0c;网站运行目录要指向/public 2&#xff0c;开启SSL&#xff0c;配置好伪静态 3&#xff0c;把网址www.niumawu.com批量替换为你自己的网址 4&#xff0c…

NOI 1818:红与黑(C++)

题目地址&#xff1a;http://noi.openjudge.cn/ch0205/1818/ 题目&#xff1a;求地图中能到达的黑砖总数 一开始没有思路&#xff0c;参考了&#xff1a;http://blog.csdn.net/c20190102/article/details/52329390 思路&#xff1a;简单搜索 使用二维数组保存地图&#xff…

ural 1818 Fair Fishermen

题意&#xff1a; 有n个人分鱼&#xff0c;第一个人先来拿&#xff0c;检查一下总数&#xff0c;如果不能恰好分成n份&#xff0c;则扔掉多余的部分&#xff0c;然后拿走自己应得的1/n&#xff0c;第二个人也重复这个步骤&#xff0c;直到第n个人&#xff0c;然后告诉你每次扔掉…

【BZOJ1818】内部白点

链接&#xff1a;BZOJ1818 解法&#xff1a;树状数组 题意转化为求线段的交点个数。 先将任一坐标离散化&#xff0c;这里以 x x 为例。之后将 x" role="presentation" style="position: relative;">xx 与 y y 坐标分别排序,求出这些线段。以…

NOI / 2.5基本算法之搜索-1818:红与黑

总时间限制: 1000ms 内存限制: 65536kB 描述 有一间长方形的房子&#xff0c;地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上&#xff0c;只能向相邻的黑色瓷砖移动。请写一个程序&#xff0c;计算你总共能够到达多少块黑色的瓷砖。 输…

Android adb shell后面可用的常用命令详细列举

adb shell 后面可以跟的常见命令有如下&#xff1a; am app_process backup bootanimation coloradjust dpm idmap input media requestsync settings svc uiautomator appops appwidget bmgr bu content hid ime interrupter pm screencap sm telecom wm dumpsys logcat getpr…

f4v文件解析

经过几天日夜,对照 flv_video_file_format_spec_v10_1.pdf,用C写了个f4v文件分析工具。也适应mp4文件分析。 原始文件为 sky.f4v 由ffmpeg生成(ffmpeg -i sky.mov sky.f4v) 链接: https://pan.baidu.com/s/1asrSPJZq1Zv4zQaYqgDsRg 密码: frec flv.exe (./flv sky.f4v)…