题意

image-20211028094841263

思路

首先，题目给定了每一条边$(u,v)$都满足二进制下表示下，$u_{(2)}$是$v_{(2)}$的一个前缀，如$u=10_{2}$，$v=101_{2}$。

由此，我们考虑构建完全二叉树这样的一个结构，则在以点$u$为根节点的子树里的任意一点$v$，均满足题目所给的前缀的条件。

为了更快的求出某点是否为子树中的一点，我们预处理一下每个点的父亲fa[now][0/1/.../20]。

数组第二维分别代表每个点的第$0,1,\dots,20$​个祖先（第$0$​​个祖先为它本身）。

而且，此处为完全二叉树，往上的祖先不会超过$20$个（实际上$17$个就好了，因为$2^{17}=131072>100000$，$20$​​个只是凑个整）。

最后，我们预处理每个点的深度dep[now]，可以得到：

当且仅当(nxt >= now) AND (fa[nxt][dep[nxt] - dep[now]] == now)时，满足nxt是now的子树中的一个节点。

预处理时间复杂度$O(nlogn)$​​。

然后，如果$u,v$两点是可达的，那么从任一点出发，都至少能够到达它们中的某一个公共祖先。

因此，在每一次询问中，我们可以考虑先找到他们的最近公共祖先。由于我们预处理了父亲数组fa[now][20]，因此可以写倍增来求$LCA$。不过对于完全二叉树，我们还可以求他们二进制中的最长公共前缀，即为对应的$LCA$。

如：$u=15=1111_{(2)}, v = 12 =1100_{(2)}, LCA(u, v)=11_{(2)}=3$

image-20211028105736772

后面发现写这种还不如写倍增LCA，太蠢了，不过如果用Trie树应该就很方便了吧…

然后我们研究一下，如何求出公共祖先到$u,v$中某一点的距离。

最初的时候，写了一个优雅（但是错的一塌糊涂，甚至套了二分试图降低复杂度）的$DP$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int search(int u, int v){
    auto nxt = lower_bound(G[u].begin(), G[u].end(), (Node){v, 0LL});
    return ((nxt == G[u].end() || (*nxt).v != v) ? INF : (*nxt).w);
}
void init(int pos){
    int now = pos, level = 0;
    dis[now][0] = 0; now >>= 1;
    while(now)
    {
        int mindis = INF;
        for(int r = pos, d = 0; r > now; r >>= 1, d++){
            if(~dis[pos][d])
                mindis = min(mindis, dis[pos][d] + search(r, now));
        }
        dis[pos][++level] = (mindis == INF ? -1 : mindis);
        now >>= 1;
    }
}

这段代码的实现的是求dis[pos][level]的值，dis[pos][0]=0，dis[pos][1]为到达点$pos$的父亲的距离的最小值，dis[pos][2]为到达点$pos$的父亲的父亲的最小值，以此类推。

但这段代码有致命的缺陷——不能够求解先往下再往上的情况（如：$2 \rightarrow 5 \rightarrow 1$​）

image-20211028113403257

HACK数据①

1
2
3
4
5
6
7
8
9
7 6
3 6 2
1 5 1
1 7 5
2 5 3
1 3 1
1 4 1
1
2 3

因此，更换思路。

考虑每个点跑一次最短路？直接对每个点跑迪杰斯特拉最短路的话，使用堆优化，得到每个点到其他点的最小距离的复杂度在$O(n^2logn)$左右，如果跑$Floyd$连数组都开不下，考虑缩小点集的范围。

我们前文说到，两个点互达，必需要经过它们的其中一个公共祖先，由此我们考虑，能不能跑每个点到达它们子树中每一个点的最短路？

分析复杂度，设极限数据为最大深度$maxdep=20$​​​​​（此处 定义根节点$dep=1$​​）的完全满二叉树。

  1. 最后一层有$2^{maxdep - 1}$​​个点

  2. 每个点的子树大小为$1$​​（包括本身），则执行次数约为$2 ^ {maxdep-1} \times (1 * log (1) )$​​​

  3. 同理可推，倒数第二层有$2^{maxdep-2}$​​个点，子树大小为$3$​​（包括本身），则执行次数约为为$2^{maxdep-2} \times (3 * log(3))$​​​

我们整合一下，得到总的操作次数为：

$\sum_{i=0}^{maxdep - 1} 2^i \times (2^{maxdep - i} - 1) \times log(2^{maxdep - i})$​​

$=\sum_{i=0}^{maxdep - 1} (2^{maxdep} - 2^i) \times (maxdep - i)$​

$\leq (maxdep - 1) \times ((maxdep - 1) \times 2 ^ {maxdep} - \sum_{i=0}^{maxdep - 1} 2^i))$​​

$=(maxdep - 1) \times ((maxdep - 1) \times 2^{maxdep} - 2^{maxdep} + 1)$​

$\leq 2^{maxdep} \times (maxdep - 1) ^ 2$​

$\approx nlog^2n$

发现数量级在$10^7$，可以通过该题，也就是说我们只需要对每个点跑一次最短路，计算某个子树的根节点到子树中所有点的最短路径就可以AC该题。

HACK数据②

顺便提供两组HACK数据：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
7 11
2 4 3
1 5 3
2 4 3
2 5 3
2 4 4
3 7 3
3 7 1
1 6 4
1 3 2
3 6 1
1 4 3
1
6 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
15 18
6 12 1
4 9 4
2 8 3
4 8 3
3 14 3
3 6 5
6 12 2
7 14 1
1 3 3
7 14 1
6 12 5
2 8 2
4 8 2
4 9 3
1 10 3
1 4 5
4 8 5
1 9 1
1
2 10

代码

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/* vegetable1024 | liushan.site | Maybe Lovely? */

#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
#pragma GCC target("avx", "sse2")
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)

#include <bits/stdc++.h>
#define maxn 100005
#define int long long
using namespace std;
int read(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9')    ch = getchar();
    while(ch >= '0' && ch <= '9')  x = x * 10 + ch - '0', ch = getchar();
    return x;
}
int n, m, q, k, head[maxn * 4];
int dep[maxn], fa[maxn][20];
struct Edge{
    int to;
    int nxt;
    int weight;
}E[maxn * 4];
void Build(int u, int v, int w){
    E[k].to = v;
    E[k].nxt = head[u];
    E[k].weight = w;
    head[u] = k++;
}
struct Node{
    int now;
    int dis;
};
bool operator < (const Node &A, const Node &B){
    return A.dis > B.dis;
}
priority_queue<Node> q1;
bool check(int now, int nxt){
    if(nxt >= now)
        return (fa[nxt][dep[nxt] - dep[now]] == now);
    return false;
}
int dis[maxn], INF = (1LL << 60);
map<int, int> finaldis[maxn];
void init(int pos){
    if(pos > n)    return;
    dis[pos] = INF;
    init((pos << 1));
    init((pos << 1) + 1);
}
void record(int s, int pos){
    if(pos > n)    return;
    finaldis[s][pos] = dis[pos];
    record(s, (pos << 1));
    record(s, (pos << 1) + 1);
}
void Dijstra(int rt){
    init(rt); dis[rt] = 0;
    q1.push((Node){rt, 0});
    while(!q1.empty()){
        Node tmp = q1.top(); q1.pop();
        int now = tmp.now, dist = tmp.dis;
        if(dist > dis[now])    continue;
        for(int i = head[now]; ~i; i = E[i].nxt){
            if(!check(rt, E[i].to))    continue;
            if(dis[E[i].to] > dis[now] + E[i].weight){
                dis[E[i].to] = dis[now] + E[i].weight;
                q1.push((Node){E[i].to, dis[E[i].to]});
            }
        }
    }
    record(rt, rt);
}
int getlca(int r1, int r2){
    vector<int> v1, v2, v3;
    bool fir1 = false, fir2 = false;
    for(int i = 18; i >= 0; i--){
        if(r1 & (1 << i))    v1.push_back(1), fir1 = true;
        else if(fir1)        v1.push_back(0);
        if(r2 & (1 << i))    v2.push_back(1), fir2 = true;
        else if(fir2)        v2.push_back(0);
    }
    int minn = min(v1.size(), v2.size());
    for(int i = 0; i < minn; i++){
        if(v1[i] != v2[i])    break;
        v3.push_back(v1[i]);
    }
    int anslen = v3.size(), res = 0;
    for(int i = anslen - 1, cnt = 0; i >= 0; i--, cnt++){
        if(v3[i])    res += (1 << cnt);
    }
    return res;
}
signed main(void)
{
    memset(head, -1, sizeof(head));
    for(int i = 0; i <= 100000; i++)    dis[i] = INF;
    n = read(); m = read();
    for(int i = 1; i <= n; i++){
        int now = i, cnt = 0;
        while(now){
            fa[i][cnt++] = now; dep[i]++; now /= 2;
        }
    }
    for(int i = 1; i <= m; i++){
        int u = read(), v = read(), w = read();
        Build(u, v, w);
        Build(v, u, w);
    }
    for(int i = n; i >= 1; i--)     Dijstra(i);
    q = read();
    while(q--){
        int s = read(), t = read(), ans = (1LL << 60);
        int lca = getlca(s, t);
        while(lca){
            int dis1 = finaldis[lca].count(s) ? finaldis[lca][s] : INF;
            int dis2 = finaldis[lca].count(t) ? finaldis[lca][t] : INF;
            ans = min(ans, dis1 + dis2);
            lca /= 2;
        }
        printf("%lld\n", ans >= INF ? -1LL : ans); 
    }
    return 0;
}

对拍器

中途因为各种BUG没调出来，上网找了个$std$​用来对拍，顺便把对拍的代码都放在这里，希望对读者有用…

fcc.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//fcc.cpp
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    int cnt = 0;
    do{
        printf("Case #%d:\n", ++cnt);
        system("maker.exe");
        system("my.exe < data.in > my.out");
        system("std.exe < data.in > std.out");
        //system("type data.in");
        //system("type my.out");
    } while (!system("fc my.out std.out"));
    return 0;
}
maker.cpp
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
//maker.cpp
#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;
int _r(int a, int b){
    return (rand() % (b - a + 1)) + a;
}
int n, m;
vector<int> s;
void getson(int ss, int now){
    if(now > n)     return;
    if(now != ss)   s.push_back(now);
    getson(ss, now * 2); 
    getson(ss, now * 2 + 1);
}
int son(int now){
    s.clear();
    getson(now, now);
    int siz = s.size();
    //cout << siz << endl;
    return s[_r(1, siz) - 1];
}
signed main(void)
{
    //time_t now = time(NULL);
    //cout << now << endl;
    srand(time(NULL));
    freopen("data.in", "w", stdout);
    n = (int)pow(2, _r(2, 3)) - 1;
    m = _r(n - 1, n + 5);
    printf("%lld %lld\n", n, m);
    int maxsize = (int)pow(2, floor(log2(1.0 * n) + 1.0));
    for(int i = 1; i <= m; i++){
        int u = _r(1, maxsize / 2 - 1);
        int v = son(u);
        //printf("GG");
        int w = _r(1, 5);
        printf("%lld %lld %lld\n", u, v, w);
    }
    int q = _r(1, 10);
    printf("%lld\n", q);
    for(int i = 1; i <= q; i++){
        int _u = _r(1, n), _v = _r(1, n);
        while(_u == _v)    _u = _r(1, n), _v = _r(1, n);
        printf("%lld %lld\n", _u, _v);
    }
    return 0;
}

另外两个程序是$std.cpp$（上网自寻）和$my.cpp$（自己的代码），然后编译后放到同一目录就可以了。