洛谷P 3398ハムスターはsugarを探して問題の報告を解きます

P 3398ハムスターがsugarを探す
タイトルの説明
ハムスターと彼の親友(zi)sugarは地下洞窟に住んでいて、各ノードの番号は1~nです.地下洞窟は木の構造です.この日ハムスターは彼の寝室(a)からレストラン(b)まで、彼の親友は同時に彼の寝室(c)から図書館まで(d).彼らは最短の道を歩きます.今、ハムスターはどこかで、彼の親友に会える可能性があるかどうか知りたいと思っています.
ハムスターはそんなに弱くて、また毎日zzqおじいさんに虐げられて、早く助けに来てください!
にゅうしゅつりょくけいしき
入力形式:
最初の行の2つの正の整数nとqは、このツリーノードの個数と問い合わせの個数を表す.
次にn−1行、各行の2つの正の整数uおよびvは、ノードuからノードvの間にエッジがあることを示す.
次にq行は、行ごとに4つの正の整数a,b,c,dがノード番号、すなわち1回のクエリを表し、その意味は上述の通りである.
出力フォーマット:
各質問に対して、共通点があれば、大文字「Y」を出力します.そうでなければ「N」を出力します.
(1)暴力木鎖断分
検索するたびにパス((a,b))を染色し、パス((c,d))を歩いて、最後に色を復元します.
Code:

#include 
#include 
#define ls id<<1
#define rs id<<1|1
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x>1;
    if(r<=Mid)
        change(ls,l,r,L,Mid,c);
    else if(l>Mid)
        change(rs,l,r,Mid+1,R,c);
    else
        change(ls,l,Mid,L,Mid,c),change(rs,Mid+1,r,Mid+1,R,c);
    color[id]=max(color[ls],color[rs]);
}
int query(int id,int l,int r,int L,int R)
{
    push_down(id,L,R);
    if(l==L&&r==R)
        return color[id];
    int Mid=L+R>>1;
    if(r<=Mid)
        return query(ls,l,r,L,Mid);
    else if(l>Mid)
        return query(rs,l,r,Mid+1,R);
    else
        return max(query(ls,l,Mid,L,Mid),query(rs,Mid+1,r,Mid+1,R));
}
char C[2]={'N','Y'};
int t_query(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]>dep[top[y]])
        {
            ans=query(1,dfn[top[x]],dfn[x],1,n);
            if(ans) return 1;
            x=f[top[x]];
        }
        else
        {
            ans=query(1,dfn[top[y]],dfn[y],1,n);
            if(ans) return 1;
            y=f[top[y]];
        }
    }
    return query(1,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),1,n);
}
void t_change(int x,int y,int c)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]>dep[top[y]])
        {
            change(1,dfn[top[x]],dfn[x],1,n,c);
            x=f[top[x]];
        }
        else
        {
            change(1,dfn[top[y]],dfn[y],1,n,c);
            y=f[top[y]];
        }
    }
    change(1,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),1,n,c);
}
int main()
{
    scanf("%d%d",&n,&q);
    memset(lazy,-1,sizeof(lazy));
    int a,b,c,d;
    for(int i=1;i

(2)手遊び観察のLCA表記
私たちは、経路を上に行くときが唯一であることを発見しました.では、交点があれば、最高点(つまりLCA)の低い経路の最高点は必ず別の経路にあります.
問題は、ポイントがパス上にあるかどうかをクエリーすることになります.2つの端点とこの点のLCAがこの点かどうかを調べるだけでいい
コードなし
2018.7.13
転載先:https://www.cnblogs.com/butterflydew/p/9305915.html