2415. [HZOI 2016]非触

【题目描述】

本题为2098的加强版。

原题地址：Asm.Def的病毒

小F最近总是和cp小E一起走，然而众所周知，衡中里是时常有级部出没来各处查男女生非正常接触(非触)的......

为了避免一起走的时候被级部抓到非触，小F特地费了半天功夫搞到了学校的地图和级部的活动规律。

学校是一个有n个节点的无向无环连通图，为了避免在某次一起走的时候和级部相遇，小F需要仔细规划每次的路线，使得他的路线和级部的活动路线不相交。为此，他需要频繁地判断图上的两条路径是否相交(经过同一节点)。

然而学校的地图实在是太大了，一会儿就把小F搞晕了，小F只得向你求助。

当然身为神犇的你是不会拒绝的......所以......

【输入格式】

第一行两个整数n,m。

接下来n-1行，每行两个整数x,y，表示(x,y)是图中的一条边。

接下来m行，每行四个整数x,y,z,w，表示询问x~y的路径是否与z~w的路径相交。

【输出格式】

对每个询问，若相交则输出一行”YES”，否则输出一行”NO”。

【样例输入】

6 5
1 2
1 3
2 4
4 5
4 6
1 1 5 6
1 2 6 3
2 3 5 6
6 4 3 1
4 3 1 2

【样例输出】

NO
YES
NO
NO
YES

【数据范围】

n,m<=1000000。

1<=x,y,z,w<=n。

【提示】

由于cogs评测机的问题，可能会爆栈，所以C++选手请在main函数的开头加入以下代码：

int __size__=128<<20;

char *__p__=(char*)malloc(__size__)+__size__;

__asm__("movl %0, %%esp\n"::"r"(__p__));

注意上述代码会占用你128MB的空间，请自行调整代码。

输入量很大，请C++选手避免使用C++的流输入输出。

请注意常数因子对于程序运行的影响。

【来源】

HZOI 2016