Tarjan缩点+LCA【洛谷P2416】 泡芙

P2416 泡芙

LCA一定要初始化倍增 pre。

话说我不初始化还能得60分。

code：

#include <iostream>

#include <cstdio>

using namespace std;

const int wx=800017;

inline int read(){

    int sum=0,f=1; char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

    while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

    return sum*f;

}

int a[wx],belong[wx],dfn[wx],low[wx],size[wx];

int head[wx],h[wx],st[wx],dep[wx],dis[wx];

int f[wx][23];

int n,m,q;

int top,tot,num,Num,col;

struct e{

    int nxt,to,dis;

}edge[wx*2];

struct ee{

    int nxt,to,dis;

}e[wx*2];

void Add(int from,int to,int dis){

    e[++Num].nxt=h[from];

    e[Num].to=to;

    e[Num].dis=dis;

    h[from]=Num;

}

void add(int from,int to,int dis){

    edge[++num].nxt=head[from];

    edge[num].to=to;

    edge[num].dis=dis;

    head[from]=num;

}

void Tarjan(int u,int fa){

    dfn[u]=low[u]=++tot;

    st[++top]=u;

    for(int i=h[u];i;i=e[i].nxt){

        int v=e[i].to;

        if(v==fa)continue;

        if(!dfn[v]) Tarjan(v,u), low[u]=min(low[u],low[v]);

        else if(!belong[v]) low[u]=min(low[u],dfn[v]);

    }

    if(low[u]==dfn[u]){

        belong[u]=++col;

        size[col]=1;

        while(st[top]!=u){

            belong[st[top]]=col;

            size[col]++;

            top--;

        }

        top--;

    }

}

void CQ(){

    for(int u=1;u<=n;u++){

        for(int i=h[u];i;i=e[i].nxt){

            int v=e[i].to;

            if(belong[u]!=belong[v])

                add(belong[u],belong[v],e[i].dis);

            else a[belong[u]]+=e[i].dis;

        }

    }

}

void dfs(int u,int fa){

    dep[u]=dep[fa]+1;

    for(int i=head[u];i;i=edge[i].nxt){

        int v=edge[i].to;

        if(v==fa)continue;

        f[v][0]=u; dis[v]=dis[u]+edge[i].dis+a[v];

        dfs(v,u);

    }

}

void pre(){

    for(int j=1;j<=20;j++)

        for(int i=1;i<=n;i++)

            f[i][j]=f[f[i][j-1]][j-1];

}

int LCA(int x,int y){

    if(dep[x]<dep[y])swap(x,y);

    for(int i=20;i>=0;i--)

        if(dep[f[x][i]]>=dep[y])x=f[x][i];

    if(x==y)return x;

    for(int i=20;i>=0;i--)

        if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];

    return f[x][0];

}

int main(){

    n=read(); m=read();

    for(int i=1;i<=m;i++){

        int x,y,z;

        x=read(); y=read(); z=read();

        Add(x,y,z); Add(y,x,z);

    }

    for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i,0);

    CQ();

    dis[belong[1]]=a[belong[1]];

	dfs(belong[1],0); pre();

    q=read();

    for(int i=1;i<=q;i++){

        int x,y;

        x=read(); y=read();

        x=belong[x]; y=belong[y];

        int lca=LCA(x,y);

        if(dis[x]+dis[y]-2*dis[lca]+a[lca]>0)puts("YES");

        else puts("NO");

    }

    return 0;

}