ACM ICPC, Damascus University Collegiate Programming Contest(2018) Solution
分类:
IT文章
•
2022-03-20 21:35:30
A：Martadella Stikes Again
水。
![]()
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 #define ll long long
6
7 int t;
8 ll R, r;
9
10 int main()
11 {
12 scanf("%d", &t);
13 while (t--)
14 {
15 scanf("%lld%lld", &R, &r);
16 if (R * R > 2ll * r * r)
17 puts("1");
18 else
19 puts("2");
20 }
21 return 0;
22 }
View Code
B：Amer and Graphs
题意：给出n条边，连续选k条边，(1 <= k <= n) 对于每一个图，有多少个图和它一样
思路：图Hash，枚举起点，再枚举长度，这样每次加边都是一条，时间复杂度O(n ^ 2)
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define INF 0x3f3f3f3f
5 #define INFLL 0x3f3f3f3f3f3f3f3f
6 #define ll long long
7 #define N 2003
8
9 typedef pair <int, int> pii;
10
11 struct simplehash
12 {
13 int len;
14 ll base, mod;
15 vector <ll> P, H;
16
17 inline simplehash() {}
18 inline simplehash(const int *ar, int n, ll b, ll m)
19 {
20 len = n; base = b, mod = m;
21 P.resize(len + 3, 1); H.resize(len + 3, 0);
22 for (int i = 1; i <= len; ++i) P[i] = (P[i - 1] * base) % mod;
23 for (int i = 1; i <= len; ++i) H[i] = (H[i - 1] + P[ar[i]]) % mod;
24 }
25
26 inline ll range_hash(int l, int r)
27 {
28 ll hashval = (H[r] - H[l - 1]) % mod;
29 return (hashval < 0 ? hashval + mod : hashval);
30 }
31 };
32
33 struct arrayhash
34 {
35 simplehash sh1, sh2;
36 inline arrayhash() {}
37 inline arrayhash(const int *ar, int n)
38 {
39 sh1 = simplehash(ar, n, 1949313259, 2091573227);
40 sh2 = simplehash(ar, n, 1997293877, 2117566807);
41 }
42 inline ll range_hash(int l, int r)
43 {
44 return (sh1.range_hash(l, r) << 32) ^ (sh2.range_hash(l, r));
45 }
46 };
47
48 int t, n, pos;
49 map <pii, int> mp;
50 unordered_map <ll, int> mp2;
51 int arr[N];
52
53 inline void Init()
54 {
55 mp.clear(); pos = 0;
56 mp2.clear();
57 }
58
59 struct Edge
60 {
61 int u, v, id;
62 inline void scan()
63 {
64 scanf("%d%d", &u, &v);
65 if (u > v) swap(u, v);
66 if (!mp.count(pii(u, v)))
67 mp[pii(u, v)] = mp.size() + 1;
68 id = mp[pii(u, v)];
69 }
70 }edge[N];
71
72 inline void Run()
73 {
74 scanf("%d", &t);
75 while (t--)
76 {
77 scanf("%d", &n); Init();
78 for (int i = 1; i <= n; ++i)
79 {
80 edge[i].scan();
81 arr[i] = edge[i].id;
82 }
83 ll ans = 0;
84 arrayhash x = arrayhash(arr, n);
85 for (int i = 1; i <= n; ++i)
86 {
87 for (int j = i; j <= n; ++j)
88 {
89 ll Hash = x.range_hash(i, j);
90 ans += mp2[Hash]++;
91 }
92 }
93 printf("%lld
", ans);
94 }
95 }
96
97 int main()
98 {
99 #ifdef LOCAL
100 freopen("Test.in", "r", stdin);
101 #endif
102
103 Run();
104
105 return 0;
106 }
View Code
C：Help Shahhoud
题意：给出A串和B串，每次可以翻转以A串中心点为轴，翻转长度为x，求长度最少使得串A变成串B，如果不行输出-1
思路：很显然要从外往里翻，如果某一段翻转性质相同，那么可以一并翻转，要特别考虑一下四个字符都相同，那么既可以翻转既可以不翻转
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 #define N 100010
6
7 int t;
8 char A[N];
9 char B[N];
10
11 int main()
12 {
13 scanf("%d",&t);
14 while(t--)
15 {
16 scanf("%s", A + 1);
17 scanf("%s", B + 1);
18 int len = strlen(A + 1);
19 int ans = 0;
20 int flag = 0;
21 for(int i = 1; i <= len / 2; ++i)
22 {
23 int l = i, r = len - i + 1;
24 if(A[l] == A[r] && A[l] == B[r] && B[l] == B[r]) continue;
25 else if(A[l] == B[r] && A[r] == B[l])
26 {
27 if(flag == 0)
28 {
29 ++ans;
30 flag = !flag;
31 }
32 }
33 else if(A[l] == B[l] && A[r] == B[r])
34 {
35 if(flag == 1)
36 {
37 ++ans;
38 flag = !flag;
39 }
40 }
41 else
42 {
43 ans = -1;
44 break;
45 }
46 }
47 if(A[(len + 1) / 2] != B[(len + 1) / 2]) ans = -1;
48 printf("%d
",ans);
49 }
50 return 0;
51 }
View Code
D：Simplified 2048
留坑。
E：Floods
题意：给出n个点形成山地（折线图），在下过一段时间的雨后留下的雨量。
思路：显然只有凹下去的点才能做出贡献。所以可以分为以下几种情况。一种是图中一部分，一种是图中二部分。对于一部分即求一个梯形面积，对于第二部分即求一个三角形的相似三角形的面积，累加一下即可。
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 #define N 100010
6
7 struct node{
8 int x,y;
9 inline node(){}
10 inline node(int x,int y) :x(x),y(y){}
11 }a[N];
12
13 int L[N];
14 int R[N];
15 int n;
16
17 int main()
18 {
19 int t;
20 scanf("%d",&t);
21 while(t--)
22 {
23 scanf("%d",&n);
24 for(int i = 1; i <= n; ++i)
25 {
26 scanf("%d %d",&a[i].x,&a[i].y);
27 }
28 int Max = 0;
29 for(int i = 1; i <= n; ++i)
30 {
31 Max = max(Max,a[i].y);
32 L[i] = Max;
33 }
34 Max = 0;
35 for(int i = n; i >= 1; --i)
36 {
37 Max = max(Max, a[i].y);
38 R[i] = Max;
39 }
40 double ans = 0;
41 for(int i = 1; i < n; ++i)
42 {
43 int top, Max, Min;
44 if(a[i].y < a[i + 1].y)
45 {
46 top = min(L[i], R[i]);
47 Max = a[i + 1].y;
48 Min = a[i].y;
49 }
50 else
51 {
52 top = min(L[i + 1], R[i + 1]);
53 Max = a[i].y;
54 Min = a[i + 1].y;
55 }
56 if(top >= Max)
57 {
58 ans += (double)(a[i + 1].x - a[i].x) * (top - a[i].y + top - a[i + 1].y) * 0.5;
59 }
60 else if(top > Min)
61 {
62 ans += (double)(a[i + 1].x - a[i].x) * (top - Min) * (top - Min) / (Max - Min) * 0.5;
63 }
64 }
65 printf("%.8f
",ans);
66 }
67 return 0;
68 }
View Code
F：Random Sort
题意：给出n个数，对标号全排列，看有多少种排列里面的数是排好的
思路：如果有相同的数，那么对于这个数它的贡献是fac[x] (fac是阶乘，x是个数)
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 const int MOD = 7901;
6
7 #define N 1010
8
9 int inv[N];
10 int n;
11 int a[N];
12
13 int main()
14 {
15 inv[0] = 1;
16 for(int i = 1; i < N; ++i)
17 {
18 inv[i] = inv[i - 1] * i % MOD;
19 }
20 int t;
21 scanf("%d",&t);
22 while(t--)
23 {
24 scanf("%d",&n);
25 int ans = 1;
26 for(int i = 1; i <= n; ++i)
27 {
28 scanf("%d",&a[i]);
29 }
30 sort(a + 1, a + 1 + n);
31 int cnt = 1;
32 for(int i = 2;i <= n; ++i)
33 {
34 if(a[i - 1] == a[i])
35 {
36 cnt++;
37 }
38 else
39 {
40 ans = ans * inv[cnt] % MOD;
41 cnt = 1;
42 }
43 }
44 ans = ans * inv[cnt] % MOD;
45 printf("%d
",ans);
46 }
47 return 0;
48 }
View Code
G：Weird Requirements
题意：给出n个数，修改最少的数字，使得gcd=x，lcm=y。
思路：显然，一个数的因数不包括gcd和lcm的因数是一定要修改的。统计这些数字的个数。当剩下的数字的因数都满足gcd与lcm的因数的时候，显然最多修改两个数字。那么当必定修改的数的个数大于等于2的时候输出这个数字即可。对于剩下的数字，求出他们的gcd与lcm。那么y/gcd为需要增加的因数，lcm/x为需要减少的因数，但是当增加的因数和减少的因数的gcd！=1时需要修改两个数字。例如gcd=6，lcm=24，五个数分别为12 12 12 12 14
![]()
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 #define N 100010
6
7 typedef long long ll;
8
9 int t, n;
10 ll arr[N];
11 ll x, y;
12
13 inline ll GCD(ll a, ll b)
14 {
15 return b == 0 ? a : GCD(b, a % b);
16 }
17
18 int main()
19 {
20 scanf("%d", &t);
21 while (t--)
22 {
23 scanf("%d", &n);
24 scanf("%lld%lld", &x, &y);
25 for (int i = 1; i <= n; ++i) scanf("%lld", arr + i);
26 if (y % x)
27 {
28 puts("-1");
29 continue;
30 }
31 if(n == 1 && x != y)
32 {
33 puts("-1");
34 continue;
35 }
36 int ans = 0;
37 ll gcd = y, lcm = x;
38 for (int i = 1; i <= n; ++i)
39 {
40 if(arr[i] % x || y % arr[i]) ++ans;
41 else
42 {
43 gcd = GCD(gcd, arr[i]);
44 lcm = lcm * arr[i] / GCD(lcm, arr[i]);
45 }
46 }
47 if (ans >= 2)
48 printf("%d
", ans);
49 else if(ans == 1)
50 {
51 if(gcd != x && lcm != y && GCD(y / gcd, lcm / x) != 1)
52 {
53 puts("2");
54 }
55 else
56 {
57 puts("1");
58 }
59 }
60 else
61 {
62 if(x == gcd && y == lcm)
63 {
64 puts("0");
65 }
66 else if(x != gcd && y != lcm && GCD(x / gcd, lcm / y) != 1)
67 {
68 puts("2");
69 }
70 else
71 {
72 puts("1");
73 }
74 }
75 }
76 return 0;
77 }
View Code
H：Shahhoud the Chief Judge
题意：一棵树，每个点有权值，sum = sgm(每个点的权值 * 路径经过它的次数)
思路：设cnt[i] 表示经过第i个点的路径数，如果存在gcd(cnt[i], cnt[j]) == 1 ，那么通过i, j 这两个数，就可以构造出所有的整数
裴蜀定理: ax + by = cgcd(a,b)； c为任意整数，当gcd(a, b)==1 时 cgcd(a, b) 为任意整数
在这棵二叉树中，必然存在这两个数
考虑深度最深的叶子结点cnt[x] = 2 * n - 1, 那么它的父亲结点的cnt[fa] = 6 * n - 11
gcd(2n - 1, 6n - 11) = gcd(2n - 1, -8) = 1 因为2n - 1 是奇数
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define INF 0x3f3f3f3f
5 #define INFLL 0x3f3f3f3f3f3f3f3f
6 #define ll long long
7 #define N 100010
8
9 inline ll GCD(ll a, ll b)
10 {
11 return (ll)b ? GCD(b, a % b) : a;
12 }
13
14 struct Edge
15 {
16 int to, nx;
17 inline Edge() {}
18 inline Edge(int to, int nx) : to(to), nx(nx) {}
19 }edge[N << 1];
20
21 int head[N], pos;
22 int t, n;
23 ll arr[N];
24 ll cnt[N];
25 ll num[N];
26 ll son[N][2];
27 int fa[N];
28 ll sum;
29
30 inline void Init()
31 {
32 memset(head, -1, sizeof head);
33 pos = 0; fa[1] = 1; sum = 0;
34 }
35
36 inline void addedge(int u, int v)
37 {
38 edge[++pos] = Edge(v, head[u]); head[u] = pos;
39 edge[++pos] = Edge(u, head[v]); head[v] = pos;
40 }
41
42 inline void DFS(int u)
43 {
44 cnt[u] = 1;
45 son[u][0] = son[u][1] = 0;
46 for (int it = head[u]; ~it; it = edge[it].nx)
47 {
48 int v = edge[it].to;
49 if (v == fa[u]) continue;
50 fa[v] = u; DFS(v);
51 cnt[u] += cnt[v];
52 if (son[u][0])
53 son[u][1] = cnt[v];
54 else
55 son[u][0] = cnt[v];
56 }
57 num[u] = (ll)(2 * n - 1) + (ll)(n - cnt[u]) * (cnt[u] - 1) * 2 + (ll)(son[u][0] * son[u][1] * 2);
58 sum += arr[u] * num[u];
59 }
60
61 inline void work()
62 {
63 if (sum == 0)
64 {
65 puts("0");
66 return;
67 }
68 int id = 1;
69 for (int i = 1; i <= n; ++i)
70 {
71 if (sum % num[i] == 0)
72 {
73 printf("1
%d
", i);
74 return;
75 }
76 if (GCD(num[i], num[fa[i]]) == 1)
77 id = i;
78 }
79 printf("2
%d %d
", fa[id], id);
80 }
81
82 inline void Run()
83 {
84 scanf("%d", &t);
85 while (t--)
86 {
87 scanf("%d", &n);
88 Init();
89 for (int i = 1; i <= n; ++i) scanf("%lld", arr + i);
90 for (int i = 1, u, v; i < n; ++i)
91 {
92 scanf("%d%d", &u, &v);
93 addedge(u, v);
94 }
95 DFS(1);
96 work();
97 }
98 }
99
100 int main()
101 {
102 #ifdef LOCAL
103 freopen("Test.in", "r", stdin);
104 #endif
105
106 Run();
107
108 return 0;
109 }
View Code
I：lldar Yalalov
题意：n堆石子，每一堆有ai个，两个人轮流取，取的操作只有两种
1° 从一堆中取一个
2°每一堆取一个，当且仅当所有堆都至少有一个才能有这个操作
思路：
如果是奇数堆，那么取一个和从所有堆中取一个的操作实际上是一样的，因为取的都是奇数个，不会影响胜负 直接% 2 判断
如果是偶数堆，并且总个数是奇数，那么先手是必胜的，因为如果最小堆里面的石子个数是奇数个，那么只要一直取这里的，如果他取一排，跟着他取
如果总个数是偶数，并且最小堆里面石子个数是偶数，那么是胜利的，因为先手改变命运的次数多一次
![]()
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 #define INF 0x3f3f3f3f
5 #define N 110
6
7 int t;
8 int n, sum, Min;
9 int arr[N];
10
11 inline bool work()
12 {
13 if (n & 1)
14 {
15 return (sum & 1);
16 }
17 if (sum & 1) return true;
18 else
19 {
20 return (Min & 1);
21 }
22 }
23
24 int main()
25 {
26 scanf("%d", &t);
27 while (t--)
28 {
29 scanf("%d", &n);
30 sum = 0, Min = INF;
31 for (int i = 1; i <= n; ++i) scanf("%d", arr + i), sum += arr[i], Min = min(Min, arr[i]);
32 puts(work() ? "Yalalov" : "Shin");
33 }
34 return 0;
35 }
View Code
J：Saeed and Folan
水。
![]()
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 int t, k;
6 int L[2], R[2], p[2], D[2];
7
8 int main()
9 {
10 scanf("%d", &t);
11 while (t--)
12 {
13 for (int i = 0; i < 2; ++i)
14 scanf("%d%d%d%d", &L[i], &R[i], &p[i], &D[i]);
15 scanf("%d", &k);
16 for (int i = 0; i < 2; ++i) if (D[i] == 0)
17 D[i] = -1;
18 int ans = 0;
19 if (p[0] == p[1]) ++ans;
20 if (p[0] == L[0]) D[0] = 1;
21 if (p[0] == R[0]) D[0] = -1;
22 if (p[1] == L[1]) D[1] = 1;
23 if (p[1] == R[1]) D[1] = -1;
24 for (int i = 1; i <= k; ++i)
25 {
26 for (int j = 0; j < 2; ++j)
27 p[j] += D[j];
28 if (p[0] == p[1]) ++ans;
29 for (int j = 0; j < 2; ++j)
30 {
31 if (p[j] == R[j]) D[j] = -1;
32 if (p[j] == L[j]) D[j] = 1;
33 }
34 }
35 printf("%d
", ans);
36 }
37 return 0;
38 }
View Code
K：Another Shortest Path Problem
题意：n个点，n条边，没有重边和自环，每次询问给出u, v 询问u -> v的最短路径
思路：这个图是一棵树加一个环，那么我们找出这个环中边权最大的边
那么最短路只有两种状况，经过这条边和不经过这条边 然后找LCA处理一下
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 typedef long long ll;
6
7 const int DEG = 20;
8 const int maxn = 1e5 + 10;
9
10 struct node{
11 int u,v;
12 ll w;
13 inline node(){}
14 inline node(int u,int v,ll w): u(u), v(v), w(w){}
15 inline bool operator < (const node &b)
16 {
17 return w < b.w;
18 }
19 }G[maxn];
20
21 struct Edge{
22 int to,nxt;
23 ll w;
24 inline Edge(){}
25 inline Edge(int to,int nxt, ll w):to(to), nxt(nxt), w(w) {}
26 }edge[maxn << 1];
27
28 int n,q;
29 int head[maxn], tot;
30 int father[maxn];
31 ll dis[maxn];
32
33 inline int find(int x)
34 {
35 return father[x] == x ? father[x] : father[x] = find(father[x]);
36 }
37
38 inline void mix(int x,int y)
39 {
40 x = find(x);
41 y = find(y);
42 if(x != y)
43 {
44 father[x] = y;
45 }
46 }
47
48 inline bool same(int x,int y)
49 {
50 return find(x) == find(y);
51 }
52
53 inline void addedge(int u,int v,ll w)
54 {
55 edge[tot] = Edge(v, head[u],w);
56 head[u] = tot++;
57 }
58
59 inline void init()
60 {
61 tot = 0;
62 memset(head, -1, sizeof head);
63 for(int i = 1; i <= n; ++i) father[i] = i;
64 }
65
66 int fa[maxn][DEG];
67 int deg[maxn];
68
69 inline void BFS(int root)
70 {
71 queue<int>q;
72 deg[root] = 0;
73 fa[root][0] = root;
74 q.push(root);
75 while(!q.empty())
76 {
77 int tmp = q.front();
78 q.pop();
79 for(int i = 1;i < DEG; ++i)
80 {
81 fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1];
82 }
83 for(int i = head[tmp]; ~i; i = edge[i].nxt)
84 {
85 int v = edge[i].to;
86 if(v == fa[tmp][0]) continue;
87 dis[v] = dis[tmp] + edge[i].w;
88 deg[v] = deg[tmp] + 1;
89 fa[v][0] = tmp;
90 q.push(v);
91 }
92 }
93 }
94
95 inline int LCA(int u, int v)
96 {
97 if(deg[u] > deg[v]) swap(u,v);
98 int hu = deg[u], hv = deg[v];
99 int tu = u,tv = v;
100 for(int det = hv - hu, i = 0;det; det >>= 1, ++i)
101 {
102 if(det & 1)
103 {
104 tv = fa[tv][i];
105 }
106 }
107 if(tu == tv) return tu;
108 for(int i = DEG - 1; i >= 0; --i)
109 {
110 if(fa[tu][i] == fa[tv][i]) continue;
111 tu = fa[tu][i];
112 tv = fa[tv][i];
113 }
114 return fa[tu][0];
115 }
116
117 inline ll query(int u,int v)
118 {
119 int root = LCA(u,v);
120 return dis[u] + dis[v] - 2 * dis[root];
121 }
122
123 int main()
124 {
125 int t;
126 scanf("%d",&t);
127 while(t--)
128 {
129 scanf("%d %d",&n,&q);
130 init();
131 int a,b;
132 ll cost;
133 for(int i = 1; i <= n; ++i)
134 {
135 scanf("%d %d %lld", &G[i].u, &G[i].v, &G[i].w);
136 }
137 sort(G + 1, G + 1 + n);
138 for(int i = 1; i <= n; ++i)
139 {
140 int u = G[i].u;
141 int v = G[i].v;
142 ll w = G[i].w;
143 if(same(u, v))
144 {
145 a = u;
146 b = v;
147 cost = w;
148 }
149 else
150 {
151 mix(u,v);
152 addedge(u,v,w);
153 addedge(v,u,w);
154 }
155 }
156 dis[1] = 0;
157 BFS(1);
158 while(q--)
159 {
160 int u,v;
161 scanf("%d %d",&u,&v);
162 ll ans = query(u, v);
163 ans = min(ans, query(u, a) + query(v, b) + cost);
164 ans = min(ans, query(v, a) + query(u, b) + cost);
165 printf("%lld
",ans);
166 }
167 }
168 return 0;
169 }
View Code
L：V--o$\_$o--V
Upsolved.
题意：
$对每一个点i求下标小于i的所有点的LCA的点权和$
思路：
考虑一个点对多个点求分别的$LCA$ 可以树剖对那些点从当前点到根打标记，那么目标点对他们求$LCA就是从当前点走到根看一下打的标记最多的是哪个$
那么此处也可以同样处理，我们需要设计一种标记，使得从该点到根的路径上所有标记点加起来恰好是当前点权值
我们可以这么处理 在这里约定$w[u] 表示点u的点权，x[u] 表示树上的标记, fa[u] 表示点u的父亲$
那么 $x[u] = w[fa[u]] - w[i]$
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define ll long long
5 #define N 200010
6 int t, n, w[N];
7 vector <int> G[N];
8
9 ll dis[N];
10 int deep[N], fa[N], sze[N], son[N], top[N], p[N], fp[N], cnt;
11 void DFS(int u)
12 {
13 sze[u] = 1;
14 for (auto v : G[u])
15 {
16 deep[v] = deep[u] + 1;
17 dis[v] = w[v] - w[u];
18 DFS(v); sze[u] += sze[v];
19 if (!son[u] || sze[v] > sze[son[u]]) son[u] = v;
20 }
21 }
22
23 void getpos(int u, int sp)
24 {
25 top[u] = sp;
26 p[u] = ++cnt;
27 fp[cnt] = u;
28 if (!son[u]) return;
29 getpos(son[u], sp);
30 for (auto v : G[u]) if (v != son[u])
31 getpos(v, v);
32 }
33
34 namespace SEG
35 {
36 ll sum[N << 2], add[N << 2], lazy[N << 2];
37 void build(int id, int l, int r)
38 {
39 sum[id] = lazy[id] = 0;
40 if (l == 1) sum[id] = dis[1];
41 if (l == r)
42 {
43 add[id] = dis[fp[l]];
44 return;
45 }
46 int mid = (l + r) >> 1;
47 build(id << 1, l, mid);
48 build(id << 1 | 1, mid + 1, r);
49 add[id] = add[id << 1] + add[id << 1 | 1];
50 }
51 void work(int id, int l, int r, int ql, int qr, ll &res)
52 {
53 if (l >= ql && r <= qr)
54 {
55 res += sum[id];
56 sum[id] += add[id];
57 ++lazy[id];
58 return;
59 }
60 if (lazy[id])
61 {
62 lazy[id << 1] += lazy[id];
63 sum[id << 1] += lazy[id] * add[id << 1];
64 lazy[id << 1 | 1] += lazy[id];
65 sum[id << 1 | 1] += lazy[id] * add[id << 1 | 1];
66 lazy[id] = 0;
67 }
68 int mid = (l + r) >> 1;
69 if (ql <= mid) work(id << 1, l, mid, ql, qr, res);
70 if (qr > mid) work(id << 1 | 1, mid + 1, r, ql, qr, res);
71 sum[id] = sum[id << 1] + sum[id << 1 | 1];
72 }
73 }
74
75 ll work(int u, int v)
76 {
77 ll res = 0;
78 while (top[u] != top[v])
79 {
80 if (deep[top[u]] < deep[top[v]]) swap(u, v);
81 SEG::work(1, 1, n, p[top[u]], p[u], res);
82 u = fa[top[u]];
83 }
84 if (deep[u] > deep[v]) swap(u, v);
85 SEG::work(1, 1, n, p[u], p[v], res);
86 return res;
87 }
88
89 void init()
90 {
91 for (int i = 1; i <= n; ++i) G[i].clear(), son[i] = 0;
92 cnt = 0;
93 }
94
95 int main()
96 {
97 scanf("%d", &t);
98 while (t--)
99 {
100 scanf("%d", &n); init();
101 for (int i = 1; i <= n; ++i) scanf("%d", w + i);
102 for (int i = 1; i <= n; ++i)
103 {
104 scanf("%d", fa + i);
105 G[fa[i]].push_back(i);
106 } dis[1] = w[1]; DFS(1); getpos(1, 1);
107 SEG::build(1, 1, n);
108 for (int i = 2; i <= n; ++i) printf("%lld%c", work(1, i), "
"[i == n]);
109 }
110 return 0;
111 }
View Code
