题解 P3398 【仓鼠找sugar】

· · 题解

独特的思路

题意：现有A,B,C,D四点，判断A到B的最短路和C到D的最短路有无交汇

以下为结论(可以大概看一下，了解大概过程，以便更好的看懂思路过程)

先套两遍lca,把A和B的，C和D的最近公共祖先求出来，然后求出A和C，A和D，B和C，B和D中lca深度最大的，把得到的深度与A和B，C和D的lca深度作比较。如果都大于等于A和B，C和D的lca深度，则输出“Y”，否则输出“N”

为什么呢？

如图，在树中，A,B的最短路走法如下

从B一直向上走，直到走到K点，然后在向下走，直到A点，我们把需要回头的K点称为

“回头点”

因为树的特性(向上的路只有一条)所以A和B的回头点就是lca(A,B),而且走法只有一条

现有A，B，C，三点，A，B的回头点是K，B和C的回头点是N。A到C的过程中，因为向上的路只有一条，所以如果N的深度小于K的深度，则A到了K点后还将继续向上走，才能到达N点，然后回头到C点。如果N的深度大于K的深度，则A还没到达K点，就到达了N点，可以回头了。

回到题目，由于我们要求两条最短路有没有交汇，转换一下，可以成为以下问题

求任意一组 不同组的两点(即A和C 或A和D 或B和C 或B和D)能否在 只能走同组之间最短路的情况下 相互到达(为什么是这样呢，各位可以自己画画图，独自探究一下)

之前我们讲过三点之间的路线规律，扩大到四个点也同样适用，如图。

我们拿B和C为例：

可以知道B和C的回头点是2，因为2的深度等于A和B的回头点的深度(大于等于都可以)，所以B到2的之间的路程都在A和B的最短路上。同理2，的深度大于C和D的回头点的深度，所以C到2的之间的路程都在C和D的最短路上。此时满足条件，输出“Y”。

再来看看这幅图

此时，B和C的回头点是2，因为2的深度小于A和B的回头点的深度，所以B到了A和B的回头点后仍然还要继续向上走到B和C的回头点，这时A和B的回头点->B和C的回头点的这一段路程是不能走的，所以B不能到C。

因为只要满足一组，而且只与回头点的深度有关，所以就像结论中所说的：然后求出A和C，A和D，B和C，B和D中lca深度最大的，把它与A和B，C和D的回头点的深度作比较，如果都大于等于，则输出“Y”，否则输出“N”。

见代码(采用树上倍增法)：

struct qqq{
    int y,next;
}a[200001];
//邻接表存树
int h[100001],d[100001],f[100001][18],v[100001];
//h：head(与邻接表相配队)，d：深度，f，v：见lca模板中的解释

关于lca的模板，本题解就不再赘述(其实是我懒)

关键代码：

for(int i=1;i<=q;i++){
    int x1,y1,x2,y2;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    int lac1=lca(x1,y1),lac2=lca(x2,y2);
    int st=max(d[lca(x1,x2)],d[lca(x1,y2)]);
    //st是存不同组的两点(即A和C 或A和D 或B和C 或B和D)的最大深度 
    st=max(st,d[lca(y1,x2)]);
    st=max(st,d[lca(y1,y2)]);
    if(st>=d[lac1]&&st>=d[lac2])cout<<"Y"<<endl;
    else cout<<"N"<<endl;
}

好了，本题解就到这了，代码有点少呵，但只要你看懂了前面的思路，自然能知道代码的实现吧，拜拜！