กำหนดให้

• $C$ เป็นเซตของ cycle ทั้งหมดในกราฟที่โจทย์กำหนดให้
• $w_p$ คือแต้มที่ได้จากการเดินบน path $p$ สำหรับ path $p$ จาก node $u$ ไป $v$ ใด ๆ (อาจเขียนเป็น $w_{u \to v}$ แทน $w_p$ ได้)

Observation 1

หากมี path จาก node $s$ ไป node $t$ หนึ่งเส้นทางเรียกว่า $p$ เราสามารถเติม cycle $c \in C$ ใด ๆ เข้าไปใน path นี้โดยแต้มจะเท่ากับ $w_p\oplus w_c$ เสมอ

ให้ $u$ เป็น node หนึ่งที่อยู่ใน $p$ และ $v$ เป็น node หนึ่งที่อยู่ใน $c$ เราสามารถเดินทางจาก $s$ ไป $t$ ได้โดย

1. เดินทางบน path จาก $s$ ไป $u$
2. เดินทางบน path จาก $u$ ไป $v$ (มีเสมอเนื่องจากโจทย์รับประกันว่าเป็น connected graph)
3. เดินทางบน cycle $c$ จนกว่าจะวนกลับมาที่ $v$ อีกครั้ง
4. เดินทางบน path จาก $v$ ไป $u$
5. เดินทางบน path จาก $u$ ไป $t$

เนื่องจากแต้มที่ได้จากการเดินทางคำนวณจาก XOR ของน้ำหนักเส้นเชื่อมทั้งหมดที่เดินผ่าน ขั้นตอนที่ 2 และ 4 จะหักล้างกัน เปรียบเสมือนว่ามีเพียงแค่ $w_p$ และ $w_c$ ที่นำมาคิดเป็นแต้มรวมเท่านั้น

หาก $p$ และ $c$ ไม่มีเส้นเชื่อมซ้ำกันเลยจะเห็นได้ชัดเจนว่าแต้มรวมย่อมเท่ากับ $w_p \oplus w_c$

กรณีที่มีเส้นเชื่อมซ้ำกัน การเดินบน cycle จะมีผลเปรียบเสมือนการเปลี่ยน path ตั้งต้น เช่น หาก $p$ คือ $1 \to 2 \to 3 \to 4 \to 5$ และ $c$ คือ $2 \to 6 \to 7 \to 4 \to 3 \to 2$ เมื่อนำมาผสมกันเป็น $1 \to 2 \to 7 \to 7 \to 4 \to 3 \to 2 \to 3 \to 4 \to 5$ จะเปรียบเสมือนการเดินทางบน $1 \to 2 \to 6 \to 7 \to 4 \to 5$ โดยตรง

จากข้อสังเกตนี้ เราสามารถสรุปได้ว่า เราสามารถสร้าง path จาก $s$ ไป $t$ ทุก path ที่เป็นไปได้ โดยใช้ path ตั้งต้นเพียง path เดียวเท่านั้นแล้วเติม cycle ตามความเหมาะสม

หากเราเลือก cycle ดี ๆ เราสามารถสร้าง path จาก $s$ ไป $t$ ให้ได้แต้มรวมมากสุด

Observation 2

บาง cycle ในกราฟสามารถสร้างได้จากการนำ cycle อื่นอย่างน้อย 2 cycle มาผสมกัน เช่น cycle $1 \to 2 \to 3 \to 1$ เมื่อนำมาผสมกับ $2 \to 3 \to 4 \to 2$ จะได้เป็น $1 \to 2 \to 4 \to 3 \to 1$ เพราะเส้นเชื่อมระหว่าง $2$ กับ $3$ ถูกหักล้างจากการเดินทางซ้ำสองครั้ง

ดังนั้น เราสามารถตัดบาง cycle ออกจากเซต $C$ ได้โดยไม่สูญเสียอิสระในการเติม cycle ให้ path ตามที่กล่าวในหัวข้อก่อนหน้า

เรียกเซตที่เล็กที่สุดที่เราสามารถนำสมาชิกมารวมกันแล้วสามารถสร้างทุก $c \in C$ ได้ว่า basis ของ $C$ หรือ fundamental cycle set โดยในที่นี้เราจะใช้สัญลักษณ์ $C^*$

วิธีสร้าง $C^*$ ที่ง่ายที่สุดคือการ Depth-first Search ออกจาก node หนึ่งในกราฟ (สมมุติว่า node $r$) จะได้ tree edge เป็นเส้นที่จะใช้ใน path ตั้งต้นระหว่างคู่ node ใด ๆ และ back edge ทั้งหมดเป็นเส้นที่ใช้ในการสร้าง fundamental cycle set (เส้นที่เชื่อมระหว่าง $u$ กับ $v$ จะทำให้เกิด cycle $u \to r \to v \to u$)

เพื่อความสะดวกในการคำนวณต่อจากนี้ ระหว่าง Depth-first Search ให้สร้าง array ไว้เพื่อเก็บค่าของ $w_{r \to u}$ สำหรับทุก node $u$

นอกจากนี้ สำหรับแต่ละ back edge ที่เชื่อมระหว่าง $u$ และ $v$ ให้เก็บแต้มที่ได้จากการเดินบน cycle นั้น คำนวณได้จาก $w_{r \to u} \oplus w_{r \to v} \oplus w_{u \to v}$ (สองพจน์แรกได้จากที่คำนวณไว้ย่อหน้าก่อนหน้า พจน์สุดท้ายคือน้ำหนักของเส้นเชื่อมระหว่าง $u$ กับ $v$)

Observation 3

ในการหา path ที่ได้แต้มมากที่สุดจาก $s$ ไป $t$ เราสามารถหา path ตั้งต้น (เรียกว่า $p$) ได้โดยเดินทางจาก $s$ ไป $r$ และจาก $r$ ไป $t$ ทำให้ได้ $w_p = w_{r\to u} \oplus w_{r \to v}$

การเลือกเติม cycle $c \in C^*$ ต่าง ๆ เข้าไปทำให้แต้มเปลี่ยน เนื่องจากเราไม่ได้สนใจว่าเติม node อะไรเข้าไปบ้างกันแน่ ต่อไปนี้ จะมองว่า $C^*$ เป็นเซตของจำนวนเต็มที่เราสามารถนำไป XOR เพื่อสร้างคำตอบได้

เช่นเดียวกับ Observation 2 ค่า $c \in C^*$ บางค่าอาจจะตัดออกได้เพราะสามารถสร้างจากค่าอื่น ๆ ใน $C^*$ ได้ เช่น หาก $C^* = \{11_2, 101_2, 110_2\}$ สามารถตัด $101_2$ ออกได้เพราะ $101_2 = 11_2 \oplus 110_2$ (หรือตัดตัวอื่นก็ได้)

กำหนดให้ $C^{**}$ แทนเซตที่เล็กที่สุดที่เป็น basis ของ $C^*$

เราสามารถหา $C^{**}$ ได้โดยใช้ขั้นตอนวิธี Gaussian Elimination โดยให้แต่ละแถวของเมทริกซ์แทนเลขแต่ละ cycle และแต่ละคอลัมน์แทนแต่ละ bit ของเลขดังกล่าว

เนื่องจากโจทย์รับประกันว่า $0 \leq c \leq 2^{63}-1$ ดังนั้นเมทริกซ์จะมีทั้งหมด $63$ คอลัมน์

สุดท้ายแล้ว เราจะได้ basis ที่ประกอบไปด้วยตัวเลขไม่เกิน $63$ ตัว โดยที่ตัวเลขแต่ละตัวจะมี most significant digit ต่างกันทั้งหมด

สำหรับ query การเดินจาก $s$ ไป $t$ สามารถหาแต้มรวมมากสุดที่เป็นไปได้โดยกำหนดให้ $ans = w_{r\to u} \oplus w_{r \to v}$ แล้วตัดสินใจว่าจะนำสมาชิกแต่ละตัวใน $C^{**}$ มา XOR หรือไม่ โดยตัดสินใจตั้งแต่ตัวเลขที่มากที่สุดมายังตัวเลขที่น้อยที่สุดแบบ greedy (หากนำมา XOR แล้วได้คำตอบดีขึ้นให้ XOR ทันที)