Not Another Path Query Problem

题目大意，给你一张图，询问 (u,v)(u,v) 是否存在一条路径，其边的按位与大于 VV

计 VV 的第一位非 00 位为 xx，在 xx 之前，任意存在一条道路满足按位与大于 2x−12^{x-1} 即可，显然，可以只取最高位。

如果找不到，另一种可能的情况是这个数前面数位和 VV 一样，后面存在一位，使得该位置 VV 为 00 并且这个数为 11

如果还找不到，看看他们的按位和是否有等于 VV 的

显然，以上可以直接用并查集来做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>

#define int long long

using namespace std;

constexpr int maxn=100100;

int n,m,q,V;
int f[70][maxn],cnt;
vector <int> valist;
map<int,int> mp;

template<typename A>
void qread(A &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
}

struct edge{
    int x,y,val;
}e[maxn*5];

int getf(int *f,int x)
{
    if(f[x]==x) return x;
    return f[x]=getf(f,f[x]);
}

signed main()
{
    ios::sync_with_stdio(false);
    qread(n);
    qread(m);
    qread(q);
    qread(V);
    int basic=0;
    auto init = [&]()
    {
        for(int j=1;j<=65;j++)
        for(int i=1;i<=n;i++)
        f[j][i]=i;
    };
    auto getval=[](int x)
    {
        return 1ll<<(x);
    };
    auto merge=[&](int x,int y,int *f)
    {
        f[getf(f,x)]=f[getf(f,y)];
    };
    init();
    int baseline=0;
    for(int i=1;i<=m;i++)
    {
        qread(e[i].x);
        qread(e[i].y);
        qread(e[i].val);
    }
    for(int i=60;i>=0;i--)
    {
        if(V&getval(i)) baseline|=getval(i);
        else if(baseline)
        {
            valist.push_back(baseline|getval(i));
            mp[baseline|getval(i)]=++cnt;
            for(int j=1;j<=m;j++)
            {
                if((e[j].val&(baseline|getval(i)))==(baseline|getval(i))) merge(e[j].x,e[j].y,f[cnt]);
            }
        }
        else{
            valist.push_back(getval(i));
            mp[getval(i)]=++cnt;
            for(int j=1;j<=m;j++)
            {
                if((e[j].val&getval(i))==getval(i)) merge(e[j].x,e[j].y,f[cnt]);
            }
        }
    }
    valist.push_back(V);
    mp[V]=++cnt;
    for(int i=1;i<=m;i++)
    {
        if((e[i].val&V)==V) merge(e[i].x,e[i].y,f[cnt]);
    }
    for(int i=1;i<=q;i++)
    {
        int x,y;
        qread(x),qread(y);
        int flag=0;
        for(auto u:valist)
        {
            if(getf(f[mp[u]],x)==getf(f[mp[u]],y)) flag=1;
        }
        if(flag) puts("Yes");
        else puts("No");
    } 
}  

/*
9 0 1 1
1 2
*/