8/21 牛客补题+cf思维+tarjan

P3398 仓鼠找 sugar

题意：在一棵树上，给定四个点，在a和b的最短路径中能否在c和d的最短路径中相遇。 思路：可看出题目给了伪标签，不是tarjan的题。一道倍增lca的题。 1.若要满足相遇，则需要a和b的lca在c和d的最短路径上；或者c和d的lca在a和b的最短路径上。 2.在树中，判断一个点是否在一条路径上，可采用距离公式：dep[x]+dep[y]-2*dep[lca(x,y)] 3.满足条件为：DIS(c,x)+DIS(d,x)==DIS(c,d)，x为a和b的lca。 代码：

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i=0;i--)
        if(fa[u][i]!=fa[v][i])
        u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}

int DIS(int x,int y)
{
    return dep[x]+dep[y]-2*dep[lca(x,y)];
}
bool check(int a,int b,int c,int d)
{
    int x=lca(a,b);
    if(DIS(c,x)+DIS(d,x)==DIS(c,d))
        return 1;
    return 0;
}
void solve()
{
    cin>>n>>q;
    for(int i=1;i>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    while(q--)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        if(check(a,b,c,d)||check(c,d,a,b))
            cout