แนวคิด
สำหรับต้นไม้ที่มี m โหนดและตัวเลขผูกกับทุกโหนด เราสามารถหักขอบไหนขอบหนึ่งได้ ซึ่งจะสร้างต้นไม้ใหม่ 2 ต้น ภารกิจคือนับจำนวนขอบที่ทำให้ Bitwise OR ของโหนดในต้นไม้สองต้นที่เกิดหลังหักขอบนั้นเท่ากัน ค่าของทุกโหนด ≤ 10^6
อินพุต
values[] = {1, 3, 1, 3}
1
/ | \
2 3 4
เอาต์พุต
2
ขอบระหว่าง 1 และ 2 สามารถหักได้ Bitwise OR ของต้นไม้สองต้นที่ได้คือ 3
ขอบระหว่าง 1 และ 4 ก็สามารถหักได้เช่นกัน
วิธีการ
ปัญหานี้แก้ได้ด้วย DFS (Depth First Search) เนื่องจากค่าโหนด ≤ 10^6 สามารถแทนได้ด้วย 22 บิตไบนารี Bitwise OR ของค่าโหนดก็แทนได้ด้วย 22 บิต วิธีคือหาจำนวนครั้งที่แต่ละบิตถูกเซ็ตในค่าทั้งหมดของ sub-tree สำหรับแต่ละขอบ ตรวจสอบแต่ละบิต 0 ถึง 21 ว่าจำนวนที่มีบิตเซ็ตเป็นศูนย์ในทั้งสองต้นไม้ที่ได้ หรือมากกว่าศูนย์ในทั้งสองต้น ถ้าเงื่อนไขเป็นจริงสำหรับทุกบิต ขอบนั้นนับในผลลัพธ์
ตัวอย่างโค้ด
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
int m1[1000], x1[22];
int a1[1000][22];
vector<vector<int>> g;
int ans1 = 0;
// DFS แบบง่าย
void dfs(int u1, int p1) {
for (int i = 0; i < g[u1].size(); i++) {
int v1 = g[u1][i];
if (v1 != p1) {
dfs(v1, u1);
// นับจำนวนครั้งแต่ละบิตถูกเซ็ตใน sub-tree ที่รากที่ v
for (int i = 0; i < 22; i++)
a1[u1][i] += a1[v1][i];
}
}
// ตรวจสอบแต่ละบิต
int pp1 = 0;
for (int i = 0; i < 22; i++) {
if (!((a1[u1][i] > 0 && x1[i] - a1[u1][i] > 0) || (a1[u1][i] == 0 && x1[i] == 0))) {
pp1 = 1;
break;
}
}
if (pp1 == 0)
ans1++;
}
// Driver code
int main() {
int n1 = 4;
g.resize(n1 + 1);
m1[1] = 1;
m1[2] = 3;
m1[3] = 1;
m1[4] = 3;
// นับบิตเซ็ตในต้นไม้ทั้งหมด
for (int i = 1; i <= n1; i++) {
int y1 = m1[i];
int k1 = 0;
while (y1 != 0) {
int p1 = y1 % 2;
if (p1 == 1) {
x1[k1]++;
a1[i][k1]++;
}
y1 = y1 / 2;
k1++;
}
}
// เพิ่มขอบ
g[1].push_back(2); g[2].push_back(1);
g[1].push_back(3); g[3].push_back(1);
g[1].push_back(4); g[4].push_back(1);
dfs(1, 0);
cout << ans1;
}
ผลลัพธ์
2
