ACM-ICPC 2018 徐州赛区网络预赛 Solution

A. Hard to prepare

题意：有n个客人做成一圈，有$2^k$种面具，对于每种面具有一种面具不能使相邻的两个人戴，共有多少种做法。

思路：把题意转化成相邻的人不能带同种面具。总数为$(2^k)^n$，减去一对相邻的客人戴同种面具$(2^k)^{(n-1)}*C(n,1)$,其中重复了两对相邻的客人戴同种面具$(2^k)^{(n-2)}*C(n,2)$，依次容斥。

最后所有人都戴同种面具的情况额外考虑，当n是奇数时，n-1对客人相同即所有人相同。n为偶数时，n-1对客人相同时用公式有重复的一轮，所以要加上。

设t=2^k

$sum_{i = 0}^{i = n - 1} C_n^i cdot t^{n - 1} * (-1)^i$ (n 是奇数)

$sum_{i = 0}^{i = n - 1} C_n^i cdot t^{n - 1} * (-1)^i + t$ (n 是偶数)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 1000010
 6 
 7 const ll MOD = (ll)1e9 + 7;
 8 
 9 int t, n, k; 
10 ll inv[N];
11 ll Bit[N];
12 ll Bitt[N];
13 
14 inline void Init()
15 {
16     inv[1] = 1;
17     for (int i = 2; i < N; ++i) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
18     Bit[0] = 1;
19     for (int i = 1; i < N; ++i) Bit[i] = (Bit[i - 1] * 2) % MOD;
20 }
21 
22 inline void init()
23 {
24     Bitt[0] = 1; ll tmp = Bit[k];
25     for (int i = 1; i <= n; ++i) Bitt[i] = (Bitt[i - 1] * tmp) % MOD; 
26 }
27 
28 inline void Run()
29 {
30     scanf("%d", &t); Init();
31     while (t--)
32     {
33         scanf("%d%d", &n, &k); 
34         if (k == 1)
35         {
36             puts("2"); 
37             continue;
38         }
39         else if (n == 1)
40         {
41             printf("%lld
",Bit[k]); 
42             continue;
43         }
44         init();
45         ll res = 0;
46         ll C = 1;
47         for (int i = 0; i < n; ++i)
48         {
49             res = (res + (C * Bitt[n - i] % MOD * ((i & 1) ? -1 : 1) + MOD) % MOD) % MOD;
50             C = C * (n - i) % MOD * inv[i + 1] % MOD;
51         }
52         res = (res + (Bit[k] * ((n & 1) ? 0 : 1)) % MOD + MOD) % MOD; 
53         printf("%lld
", res);
54     }
55 }
56 
57 int main()
58 {
59     #ifdef LOCAL  
60         freopen("Test.in", "r", stdin);
61     #endif  
62 
63     Run();
64     return 0;
65 }

View Code

B. BE, GE or NE

题意：每一轮有三种操作，加上a 减去b 或者取负当且仅当 a, b, c 不为0时，对应的操作有效，给出一个上界和一个下界大于等于上界就是 Good Ending 小于等于下界就是 Bad Ending 否则就是 Normal Ending 两个人轮流操作，第一个人想要Good Ending 第二个人想要 Bad Ending 两个人操作最优，求最后的结局

思路：dp[i][j] 表示第几轮数字是多少的时候，记忆化爆搜因为数字在$[-100, 100]$

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 typedef long long ll;
  6 
  7 const int MOD = (int)1e9 + 7;
  8 const int INF = 0x3f3f3f3f;
  9 const ll INFLL = 0x3f3f3f3f3f3f3f3f;
 10 const int maxn = (int)1e3 + 10;
 11 
 12 struct node {
 13     int a, b, c;
 14     inline node() {}
 15     inline node(int a, int b, int c) :a(a), b(b), c(c) {}
 16 }arr[maxn];
 17 
 18 int n, m, l, k;
 19 int type[maxn][maxn];//1 good  0 normal  -1 bad
 20 int vis[maxn][maxn];
 21 
 22 inline void Init()
 23 {
 24     memset(vis, 0, sizeof vis);
 25     memset(type, 0, sizeof type);
 26 }
 27 
 28 inline int DFS(int idx, int state)
 29 {
 30     if (idx > n)
 31     {
 32         if (state <= l) return -1;
 33         else if (state >= k) return 1;
 34         else return 0;
 35     }
 36     if (vis[idx][state]) return type[idx][state];
 37     vis[idx][state] = 1;
 38     int res = 0;
 39     //a
 40     int A = 2, B = 2, C = 2;
 41     if (arr[idx].a)
 42     {
 43         A = DFS(idx + 1, min(100, state + arr[idx].a));
 44     }
 45     //b
 46     if (arr[idx].b)
 47     {
 48         B = DFS(idx + 1, max(-100, state - arr[idx].b));
 49     }
 50     //c
 51     if (arr[idx].c)
 52     {
 53         C = DFS(idx + 1, max(-100, min(100, state * -arr[idx].c)));
 54     }
 55     if ((A == 1 || A == 2)&& (B == 1 || B == 2) && (C == 1 || C == 2) && (idx & 1) == 0)
 56     {
 57         type[idx][state] = 1;
 58         return 1;
 59     }
 60     else if ((A == -1 || A == 2) && (B == -1 || B == 2) && (C == -1 || C == 2) && (idx & 1) == 1)
 61     {
 62         type[idx][state] = -1;
 63         return -1;
 64     }
 65     else if ((A == 1 || B == 1 || C == 1) && (idx & 1) == 1)
 66     {
 67         type[idx][state] = 1;
 68         return 1;
 69     }
 70     else if ((A == -1 || B == -1 || C == -1) && (idx & 1) == 0)
 71     {
 72         type[idx][state] = -1;
 73         return -1;
 74     }
 75     else
 76     {
 77         type[idx][state] = 0;
 78         return 0;
 79     }
 80 }
 81 
 82 inline void RUN()
 83 {
 84     while (~scanf("%d %d %d %d", &n, &m, &k, &l))
 85     {
 86         Init(); 
 87         for (int i = 1; i <= n; ++i)
 88         {
 89             scanf("%d %d %d", &arr[i].a, &arr[i].b, &arr[i].c);
 90         }
 91         int ans = DFS(1, m);
 92         if (ans == 1)
 93         {
 94             puts("Good Ending");
 95         }
 96         else if (ans == -1)
 97         {
 98             puts("Bad Ending");
 99         }
100         else
101         {
102             puts("Normal Ending");
103         }
104     }
105 }
106 
107 int main()
108 {
109 #ifdef LOCAL_JUDGE
110     freopen("Text.txt", "r", stdin);
111 #endif // LOCAL_JUDGE
112 
113     RUN();
114 
115 #ifdef LOCAL_JUDGE
116     fclose(stdin);
117 #endif // LOCAL_JUDGE
118 }

View Code

C. Cacti Lottery

留坑。

D. Easy Math

留坑。

E. End Fantasy VIX

留坑。

F. Features Track

水。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 100010
 5 #define ll long long
 6 
 7 typedef pair <ll, ll> pii;
 8 
 9 int t, n, tot;
10 ll ans, x, y;
11 map <pii, pii> mp; 
12 
13 inline void Run()
14 {
15     scanf("%d", &t);
16     while (t--)
17     {
18         scanf("%d", &n); mp.clear(); ans = 0;
19         for (int i = 1; i <= n; ++i)
20         {
21             scanf("%d", &tot);
22             for (int j = 1; j <= tot; ++j)
23             {
24                 scanf("%lld%lld", &x, &y);
25                 if (mp[pii(x, y)].second == i - 1) ++mp[pii(x, y)].first;
26                 else if (mp[pii(x, y)].second == i) continue;
27                 else mp[pii(x, y)].first = 1;
28                 ans = max(ans, mp[pii(x, y)].first);
29                 mp[pii(x, y)].second = i;
30             }
31         }
32         printf("%lld
", ans);
33     }
34 }
35 
36 int main()
37 {
38     #ifdef LOCAL  
39         freopen("Test.in", "r", stdin);
40     #endif  
41 
42     Run();
43     return 0;
44 }

View Code

G. Trace

题意：每次给出一个点，然后就会形成两条线，如果后面的矩形覆盖了前面的边，那么这条边就消失了，最后求剩下的边是多少

思路：分别处理x轴，y轴，然后排序，然后扫过去，每次加上自己的边长以及减去标号比自己小的并且长度比自己高的个数乘自己的边长

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define N 50010
  5 #define ll long long
  6 
  7 int n;
  8 
  9 struct node
 10 {
 11     int l, r;
 12     int lazy, sum;
 13     inline node() {}
 14     inline node(int _l, int _r)
 15     {
 16         l = _l, r = _r;
 17         lazy = -1;
 18         sum = 0;
 19     }
 20 }tree[N << 2];
 21 
 22 inline void pushup(int id)
 23 {
 24     tree[id].sum = tree[id << 1].sum + tree[id << 1 | 1].sum;
 25 }
 26 
 27 inline void pushdown(int id)
 28 {
 29     if (tree[id].l >= tree[id].r) return;
 30     if (~tree[id].lazy) 
 31     {
 32         int lazy = tree[id].lazy; tree[id].lazy = -1;
 33         tree[id << 1].lazy = tree[id << 1 | 1].lazy = lazy;
 34         tree[id << 1].sum = tree[id << 1 | 1].sum = 0;
 35     }
 36 }
 37 
 38 inline void build(int id, int l, int r) 
 39 {
 40     tree[id] = node(l, r);
 41     if (l == r) return;
 42     int mid = (l + r) >> 1;
 43     build(id << 1, l, mid);
 44     build(id << 1 | 1, mid + 1, r);
 45 }
 46 
 47 inline void update(int id, int l, int r, int val)
 48 {
 49     if (tree[id].l >= l && tree[id].r <= r)
 50     {
 51         tree[id].sum = val; 
 52         tree[id].lazy = val;
 53         return;
 54     }
 55     pushdown(id);
 56     int mid = (tree[id].l + tree[id].r) >> 1;
 57     if (l <= mid) update(id << 1, l, r, val); 
 58     if (r > mid) update(id << 1 | 1, l, r, val);
 59     pushup(id);
 60 }
 61 
 62 inline int query(int id, int l, int r)
 63 {
 64     if (tree[id].l >= l && tree[id].r <= r) return tree[id].sum;
 65     pushdown(id);
 66     int mid = (tree[id].l + tree[id].r) >> 1;
 67     int res = 0;
 68     if (l <= mid) res += query(id << 1, l, r);
 69     if (r > mid) res += query(id << 1 | 1, l, r);
 70     return res;
 71 }
 72 
 73 struct DT
 74 {
 75     int pos;
 76     ll x, y;
 77     inline void scan(int _pos)
 78     {
 79         pos = _pos;
 80         scanf("%lld%lld", &x, &y);
 81     }
 82 }arr[N];
 83 
 84 inline bool cmp1(DT a, DT b)
 85 {
 86     return a.x < b.x;
 87 }
 88 
 89 inline bool cmp2(DT a, DT b)
 90 {
 91     return a.y < b.y;
 92 }
 93 
 94 inline void Run()
 95 {
 96     while (scanf("%d", &n) != EOF)
 97     {
 98         for (int i = 1; i <= n; ++i) arr[i].scan(i);
 99         build(1, 1, n); 
100         sort(arr + 1, arr + 1 + n, cmp1);
101         ll res = 0;
102         for (int i = 1; i <= n; ++i)
103         {
104             res += arr[i].y;
105             int pos = query(1, 1, arr[i].pos);
106             res -= arr[i].y * pos; 
107             update(1, 1, arr[i].pos, 0);
108             update(1, arr[i].pos, arr[i].pos, 1);
109         }
110         sort(arr + 1, arr + 1 + n, cmp2);
111         update(1, 1, n, 0); 
112         for (int i = 1; i <= n; ++i)
113         {
114             res += arr[i].x;
115             int pos = query(1, 1, arr[i].pos);
116             res -= arr[i].x * pos;
117             update(1, 1, arr[i].pos, 0);
118             update(1, arr[i].pos, arr[i].pos, 1);
119         }
120         printf("%lld
", res);
121     }
122 }
123 
124 int main()
125 {
126     #ifdef LOCAL  
127         freopen("Test.in", "r", stdin);
128     #endif  
129 
130     Run();
131     return 0;
132 }

View Code

栈维护：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 50010
 5 #define ll long long
 6 
 7 int n;
 8 
 9 struct node
10 {
11     int pos; 
12     ll x, y;
13     inline void scan(int _pos)
14     {
15         pos = _pos;
16         scanf("%lld%lld", &x, &y);
17     }
18 }arr[N];
19 
20 inline bool cmp1(node a, node b)
21 {
22     return a.x < b.x;
23 }
24 
25 inline bool cmp2(node a, node b)
26 {
27     return a.y < b.y;
28 }
29 
30 inline void Run()
31 {
32     while (scanf("%d", &n) != EOF)
33     {
34         for (int i = 1; i <= n; ++i) arr[i].scan(i);
35         sort(arr + 1, arr + 1 + n, cmp1); 
36         ll res = 0;
37         stack<int>s;
38         for (int i = 1; i <= n; ++i)
39         {
40             res += arr[i].y;
41             int cnt = 0;
42             while (!s.empty() && s.top() < arr[i].pos)
43             {
44                 cnt++;
45                 s.pop();
46             }
47             res -= cnt * arr[i].y;
48             s.push(arr[i].pos);
49         }
50         while (!s.empty())
51         {
52             s.pop();
53         }
54         sort(arr + 1, arr + 1 + n, cmp2);
55         for (int i = 1; i <= n; ++i)
56         {
57             res += arr[i].x;
58             int cnt = 0;
59             while (!s.empty() && s.top() < arr[i].pos)
60             {
61                 cnt++;
62                 s.pop();
63             }
64             res -= cnt * arr[i].x;
65             s.push(arr[i].pos);
66         }
67         printf("%lld
", res);
68     }
69 }
70 
71 int main()
72 {
73     #ifdef LOCAL_JUDGE
74         freopen("Text.txt", "r", stdin);
75     #endif  
76 
77     Run();
78     return 0;
79 }

View Code

H. Ryuji doesn't want to study

题意：两个操作，第一种是查询$[L, R]$ 区间内 $a[L] * len + a[L + 1] * (len - 1) + ... + a[R] * 1$

第二种是改变一个数

思路：线段树，记录两个值，一个是sum,另一个是 $a[L] * len + a[L + 1] * (len - 1) + ... + a[R] * 1$

考虑合并的时候显然两个区间合并，相当于左区间的长度增加了右区间的长度，那么只需要多加上左区间的sum * 右区间长度

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define N 100010
  5 #define ll long long
  6 
  7 int n, q;
  8 ll arr[N];
  9 
 10 struct node
 11 {
 12     int l, r;
 13     ll sum1, sum2;
 14     inline node() {}
 15     inline node(int l, int r, ll sum1, ll sum2) : l(l), r(r), sum1(sum1), sum2(sum2) {}
 16 }tree[N << 2];
 17 
 18 inline void pushup(int id)
 19 {
 20     tree[id].sum1 = tree[id << 1].sum1 + tree[id << 1 | 1].sum1;
 21     tree[id].sum2 = tree[id << 1 | 1].sum2 + tree[id << 1].sum2 + tree[id << 1].sum1 * (tree[id << 1 | 1].r - tree[id << 1 | 1].l + 1);
 22 }
 23 
 24 inline void build(int id, int l, int r)
 25 {
 26     tree[id] = node(l, r, 0, 0);
 27     if (l == r)
 28     {
 29         tree[id].sum1 = arr[tree[id].l];
 30         tree[id].sum2 = arr[tree[id].l];
 31         return;
 32     }
 33     int mid = (l + r) >> 1;
 34     build(id << 1, l, mid);
 35     build(id << 1 | 1, mid + 1, r); 
 36     pushup(id);
 37 }
 38 
 39 inline void update(int id, int pos, ll val)
 40 {
 41     if (tree[id].l == tree[id].r)
 42     {
 43         tree[id].sum1 = val;
 44         tree[id].sum2 = val;
 45         return;
 46     }
 47     int mid = (tree[id].l + tree[id].r) >> 1;
 48     if (pos <= mid) update(id << 1, pos, val);
 49     else update(id << 1 | 1, pos, val);
 50     pushup(id);
 51 }
 52 
 53 ll anssum;
 54 
 55 inline void query(int id, int l, int r)
 56 {
 57     if (tree[id].l >= l && tree[id].r <= r)
 58     {
 59         anssum += tree[id].sum2 + tree[id].sum1 * (r - tree[id].r);
 60         return;
 61     }
 62     int mid = (tree[id].l + tree[id].r) >> 1;
 63     if (l <= mid) query(id << 1, l, r);
 64     if (r > mid) query(id << 1 | 1, l, r);
 65 }
 66 
 67 inline void Run()
 68 {
 69     while (scanf("%d%d", &n, &q) != EOF)
 70     {
 71         for (int i = 1; i <= n; ++i) scanf("%lld", arr + i);
 72         build(1, 1, n);
 73         int op, a, b; ll v;
 74         for (int i = 1; i <= q; ++i)
 75         {
 76             scanf("%d", &op);
 77             if (op == 1)
 78             {
 79                 scanf("%d%d", &a, &b);
 80                 anssum = 0; query(1, a, b);
 81                 printf("%lld
", anssum);
 82             }
 83             else
 84             {
 85                 scanf("%d%lld", &a, &v);
 86                 update(1, a, v);
 87             }
 88         }
 89     }
 90 }
 91 
 92 int main()
 93 {
 94     #ifdef LOCAL  
 95         freopen("Test.in", "r", stdin);
 96     #endif  
 97 
 98     Run();
 99     return 0;
100 }

View Code

I. Characters with Hash

水。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 
 7 const int MOD = (int)1e9 + 7;
 8 const int INF = 0x3f3f3f3f;
 9 const ll INFLL = 0x3f3f3f3f3f3f3f3f;
10 const int maxn = (int)1e6 + 10;
11 
12 int n;
13 char s[10];
14 char str[maxn];
15 
16 int arr[maxn];
17 
18 inline void RUN()
19 {
20     int t;
21     scanf("%d", &t);
22     while (t--)
23     {
24         scanf("%d", &n);
25         scanf("%s", s);
26         scanf("%s", str);
27         int len = strlen(str);
28         for (int i = 0; i < len; ++i)
29         {
30             arr[i] = abs(str[i] - s[0]);
31         }
32         int ans = 2 * len;
33         for (int i = 0; i < len; ++i)
34         {
35             if (arr[i] == 0)
36             {
37                 ans -= 2;
38             }
39             else if (arr[i] < 10)
40             {
41                 ans -= 1;
42                 break;
43             }
44             else
45             {
46                 break;
47             }
48         }
49         if (ans == 0) ans = 1;
50         printf("%d
", ans);
51     }
52 }
53 
54 int main()
55 {
56 #ifdef LOCAL_JUDGE
57     freopen("Text.txt", "r", stdin);
58 #endif // LOCAL_JUDGE
59 
60     RUN();
61 
62 #ifdef LOCAL_JUDGE
63     fclose(stdin);
64 #endif // LOCAL_JUDGE
65 }

View Code

J. Maze Designer
题意：有一个$n * m$ 的迷宫，我们要建一些边使得其构成迷宫，要花费最小，然后给出两个点求最短距离

思路：花费最小，其实就是求最大生成树，那么剩下的边则为迷宫

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define N 300010
  5 #define ll long long
  6 
  7 struct Edge
  8 {
  9     int to, nx; ll w; 
 10     inline Edge() {}
 11     inline Edge(int to, int nx, ll w) : to(to), nx(nx), w(w) {}
 12     inline bool operator < (const Edge &r) const
 13     {
 14         return w > r.w;  
 15     }
 16 }edge[N << 1], ed[N << 1]; 
 17 
 18 int n, m, q;
 19 int head[N], pos, cnt, tot;
 20 int pre[N], F[N << 1], P[N], rmq[N << 1];
 21 ll dist[N];  
 22 
 23 inline void Init()
 24 {
 25     memset(head, -1, sizeof head); pos = 0; cnt = 0; dist[1] = 0; tot = 0;
 26     for (int i = 1; i <= n * m; ++i) pre[i] = i;
 27 }
 28 
 29 inline void addedge(int u, int v, ll w) 
 30 {
 31     edge[++pos] = Edge(v, head[u], w); head[u] = pos;
 32 }
 33 
 34 struct ST
 35 {
 36     int mm[N << 1];
 37     int dp[N << 1][20];
 38     inline void init(int n)
 39     {
 40         mm[0] = -1;
 41         for (int i = 1; i <= n; ++i)
 42         {
 43             mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];
 44             dp[i][0] = i;
 45         }
 46         for (int j = 1; j <= mm[n]; ++j)
 47         {
 48             for (int i = 1; i + (1 << j) - 1 <= n; ++i)
 49             {
 50                 dp[i][j] = rmq[dp[i][j - 1]] < rmq[dp[i + (1 << (j - 1))][j - 1]] ? dp[i][j - 1] : dp[i + (1 << (j - 1))][j - 1];
 51             }
 52         }
 53     }
 54     inline int query(int a, int b)
 55     {
 56         if (a > b) swap(a, b);
 57         int k = mm[b - a + 1];
 58         return rmq[dp[a][k]] <= rmq[dp[b - (1 << k) + 1][k]] ? dp[a][k] : dp[b - (1 << k) + 1][k];
 59     }
 60 }st;
 61 
 62 inline void DFS(int u, int pre, int dep)
 63 {
 64     F[++tot] = u;
 65     rmq[tot] = dep;
 66     P[u] = tot;
 67     for (int it = head[u]; ~it; it = edge[it].nx)
 68     {
 69         int v = edge[it].to;
 70         if (v == pre) continue;
 71         dist[v] = dist[u] + 1;
 72         DFS(v, u, dep + 1);
 73         F[++tot] = u;
 74         rmq[tot] = dep;
 75     }
 76 }
 77 
 78 inline void Lca_Init(int root, int node_num)
 79 {
 80     DFS(root, root, 0);
 81     st.init(2 * node_num - 1);
 82 }
 83 
 84 inline int query_lca(int u, int v)
 85 {
 86     return F[st.query(P[u], P[v])]; 
 87 }
 88 
 89 inline int find(int x)
 90 {
 91     if (pre[x] != x)
 92         pre[x] = find(pre[x]); 
 93     return pre[x];
 94 }
 95 
 96 inline void join(int x, int y)
 97 {
 98     int fx = find(x), fy = find(y);
 99     if (fx != fy)
100         pre[fx] = fy;
101 }
102 
103 inline void Kruskal()
104 {
105     sort(ed + 1, ed + 1 + cnt); 
106     int Count = 1;
107     for (int i = 1; i <= cnt; ++i)
108     {
109         int u = ed[i].to, v = ed[i].nx;
110         if (find(u) == find(v)) continue; 
111         addedge(u, v, ed[i].w); addedge(v, u, ed[i].w);
112         join(u, v);
113         ++Count;
114         if (Count == n * m)    return;   
115     }
116     return;
117 }
118 
119 inline void Run()
120 {
121     while (scanf("%d%d", &n, &m) != EOF)
122     {
123         Init();
124         char dir; ll w; int u, v;
125         for (int i = 1; i <= n; ++i)
126         {
127             for (int j = 1; j <= m; ++j)
128             {
129                 for (int k = 0; k < 2; ++k)
130                 {
131                     scanf(" %c %lld", &dir, &w);
132                     u = (i - 1) * n + j;
133                     if (dir == 'X') continue; 
134                     if (dir == 'D') v = i * n + j;
135                     else if (dir == 'R') v = (i - 1) * n + j + 1;
136                     ed[++cnt] = Edge(u, v, w); 
137                 } 
138             }
139         }
140         Kruskal(); Lca_Init(1, n * m); 
141         int x[2], y[2];  
142         scanf("%d", &q);
143         for (int i = 1; i <= q; ++i)
144         {
145             scanf("%d%d%d%d", &x[0], &y[0], &x[1], &y[1]);
146             u = (x[0] - 1) * n + y[0], v = (x[1] - 1) * n + y[1];
147             int lca = query_lca(u, v);
148             //printf("%d %d %d
", u, v, lca);
149             printf("%lld
", dist[u] + dist[v] - 2 * dist[lca]); 
150         }
151         
152     }
153 }
154 
155 int main()
156 {
157     #ifdef LOCAL  
158         freopen("Test.in", "r", stdin);
159     #endif   
160 
161     Run();
162     return 0;
163 }

View Code

K. Morgana Net

留坑。