题目描述

“我有个愿望，我希望在灿烂千阳时遇见你。”

这是个有n个点的世界，有m条无向边连接着这n个点，但是不保证点之间能够互相到达。

“这个世界的夕阳，只在奇数长的简单路径的尽头。”一个神如是说。

于是我想知道对于一个点对(x,y)，x到y之间的所有简单路径中是否存在长度为奇数的路径，只有这样，我才能找到存在有夕阳的路。

数据范围

对于50%的数据，1≤n,m,q≤500

对于100%的数据,,1≤n,q,m≤100000

保证没有自环与重边。

解法

首先判断每条边是否是存在于一个奇数长度的简单环中，标记为奇边。①

然后对原图生成树， 对于询问(x,y)，回答“Yes”当且仅当：

x,y隶属于同一棵树中，并且满足以下条件其中之一：

1.x,y在树上路径的距离为奇数；

2.x,y在树上路径上有一条边被标记为奇边。②

①实现：

对原图进行tarjan点双连通分量，对于一条虚边(x,y)，如果x,y在tarjan树上的距离为偶数，那么加上这条边的话，x,y一定在一个包含(x,y)的奇环中，所以(x,y)就是一条奇边。

tarjan树：由tarjan的遍历呈树形，这棵树姑且称为tarjan树。

虚边：x,y存在一条边，且x比y更晚入栈，这样的边姑且称为虚边。

如果(x,y)是一条奇边，那么包含这条边的点双连通分量的所有边都是奇边。

简单证明：任取点双连通分量里面的一条边(x,y)，如果树上路径(x,y)不是奇边，那么一定可以反向走找到一条包含奇边的路径。

②实现：

LCA求树上和。

代码

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#define ll long long

#define ln(x,y) int(log(x)/log(y))

using namespace std;

const char* fin="sunset.in";

const char* fout="sunset.out";

const int inf=0x7fffffff;

const int maxn=100007,maxm=maxn*2,maxk=20;

int n,m,i,j,k,t;

int fi[maxn],la[maxm],ne[maxm],tot;

int color,co[maxn];

int stack[maxn],low[maxn],dfn[maxn],num;

int de[maxn],dad[maxn],bitch[maxn];

int fa[maxn][maxk],va[maxn][maxk];

bool bz[maxn],az[maxn],cz[maxm];

int c[maxn];

bool re[maxn];

int getdad(int x){

    if (dad[x]==x) return x;

    dad[x]=getdad(dad[x]);

    return dad[x];

}

void add_line(int x,int y){

    tot++;

    ne[tot]=fi[x];

    la[tot]=y;

    fi[x]=tot;

}

void tarjan(int v,int from){

    int i,j,k;

    co[v]=color;

    dfn[v]=low[v]=++num;

    de[v]=de[from]+1;

    //bz[stack[j=++stack[0]]=v]=true;

    for (k=fi[v];k;k=ne[k])

        if (!cz[(k+1)/2]){

            j=stack[0];

            stack[++stack[0]]=(k+1)/2;

            cz[(k+1)/2]=true;

            if (!dfn[la[k]]){

                fa[la[k]][0]=v;

                tarjan(la[k],v);

                low[v]=min(low[v],low[la[k]]);

                if (low[la[k]]>=dfn[v]){

                    bool haveji=false;

                    c[0]=0;

                    while (stack[0]>j){

                        i=stack[stack[0]];

                        haveji|=az[i];

                        if (!re[la[i*2]]) c[++c[0]]=la[i*2],re[la[i*2]]=true;

                        if (!re[la[i*2-1]]) c[++c[0]]=la[i*2-1],re[la[i*2-1]]=true;

                        stack[0]--;

                    }

                    for (i=1;i<=c[0];i++) {

                        if (haveji && re[fa[c[i]][0]]) va[c[i]][0]=1;

                    }

                    for (i=1;i<=c[0];i++) re[c[i]]=false;

                }

            }else{

                low[v]=min(low[v],low[la[k]]);

                if (de[la[k]]%2==de[v]%2) az[(k+1)/2]=true;

            }

        }

}

void up(int &a,int i,int &k){

    k+=va[a][i];

    a=fa[a][i];

}

int lca(int a,int b){

    int i,j,k=0;

    if (de[a]<de[b]) swap(a,b);

    for (i=ln(de[a]-de[b],2);i>=0;i--) if (de[fa[a][i]]>de[b]) up(a,i,k);

    if (de[a]!=de[b]) up(a,0,k);

    for (i=ln(de[a],2);i>=0;i--) if (fa[a][i]!=fa[b][i]) up(a,i,k),up(b,i,k);

    if (a!=b) up(a,0,k),up(b,0,k);

    return k;

}

int main(){

    freopen(fin,"r",stdin);

    freopen(fout,"w",stdout);

    scanf("%d%d",&n,&m);

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

        scanf("%d%d",&j,&k);

        add_line(j,k);

        add_line(k,j);

    }

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

    //for (i=1;i<=n;i++) if (az[dad[i]]) va[i][0]=1;

    for (i=1,j=ln(n,2);i<=j;i++)

        for (k=1;k<=n;k++){

            fa[k][i]=fa[fa[k][i-1]][i-1];

            va[k][i]=va[fa[k][i-1]][i-1]+va[k][i-1];

        }

    scanf("%d",&t);

    for (;t;t--){

        scanf("%d%d",&j,&k);

        if (co[j]==co[k] && (de[j]%2!=de[k]%2 || lca(j,k))) printf("Yes\n");

        else printf("No\n");

    }

    return 0;

}

启发

点双连通分量

在一棵生成树上，如果一个点x，不存在一个son[x]有虚边连向x的祖先，那么x就是一个割点；

依靠割点找出点双连通分量。

路径询问问题

先对原图进行生成树，再考虑会不会简单一些呢？

（留坑待填）