Garden | o67_oct_c2_goatpay Tutorial

โจทย์

มีต้นไม้อยู่ต้นหนึ่งที่มีจุดยอด $0, 1, 2, \dots, N-1$ และมีเส้นเชื่อม $e_{i} = (u_i, v_i)$ เมื่อ $u_i, v_i$ เป็นหมายเลขของจุดยอด และ $u_i \neq v_i$ สำหรับ $i = 1, 2, 3, \dots N-2$ ในแต่ละเส้นเชื่อมจะมีนำ้หนัก $w_{i}$ และสี $c_{i}$ มีการดำเนินการทั้งหมด 2 แบบ

ถามว่าจาก $u$ เดินไปหา $v$ จะใช้การ XOR น้ำหนักทั้งหมดเท่าใด เมื่อคิดน้ำหนักเฉพาะเส้นเชื่อมในเส้นทางที่มีสี $x$ เท่านั้น
ทำการเปลี่ยนน้ำหนักของเส้นเชื่อมที่ $id$ ให้กลายเป็น $d$

โดยที่ $N \le 10^6$ , $Q \le 10^6$ และจำนวนสีทั้งหมดไม่เกิน $N$ แบบ

หมายเหตุ

ในเฉลยนี้จะเขียนวิธีแก้ปัญหาสำหรับจำนวนสีน้อย ๆ ส่วนคำแนะนำเพิ่มเติมแนะนำให้ไปดูได้ที่ คำแนะนำ

ปัญหาย่อยที่ต้นไม้เป็นเส้นตรง

เนื่องจากต้นไม้เป็นเส้นตรงจึงสามารถมองเป็นอาเรย์ของเลขธรรมดาได้ เมื่อต้องการหาว่าตั้งแต่ index ที่ $u$ ไปถึง $v$ จะใช้การ XOR น้ำหนักทั้งหมดเท่าใด สามารถใช้ Segment Tree ในการแก้ปัญหานี้ได้ โดย Segment Tree จะไม่ได้มีเพียง 1 ต้นแต่มีถึง $C$ ต้นเพื่อเก็บค่าการ XOR ในช่วงของแต่ละสีได้

ปัญหาย่อยที่มีจำนวนจุดยอดของต้นไม้ไม่เกิน 100,000 และมีการทำการดำเนินการไม่เกิน 100,000 ครั้ง

ในปัญหาย่อยนี้เป็นปัญหาที่สามารถมองได้ชัดเจนว่าสามารถใช้ Heavy Light Decomposition (HLD) ในการแก้ปัญหา โดยการทำ HLD จะทำการแตกต้นไม้ออกมาเป็นช่วง (สามารถดูเพิ่มเติมได้ที่ คลิปของพี่ Krist) จากนั้นทำการเก็บแต่ละช่วงไว้ใน Segment Tree ของแต่ละสีได้เลย

ปัญหาเต็ม

ผู้แต่งคิดว่าจากการทำ Heavy Light Decomposition ในปัญหาย่อยก่อนหน้าจะทำให้เราสามารถสังเกตได้ว่า ไม่จำเป็นต้องไต่ไปที่ Lowest Common Ancestor ทุกครั้ง เนื่องจากคุณสมบัติบางอย่างของ XOR

สมบัติที่น่าสนใจของ XOR: $X \oplus X = 0$

จากการสังเกตจะพบว่าสามารถใช้เพียง Euler Tour Techinque เพื่อเก็บเวลาเข้าและออกของแต่ละช่วง (พิจารณาช่วงคล้ายวิธีแบบ HLD โดยไม่ต้องคิดว่า Child ไหนเป็น Heavy) จากนั้น เมื่อต้องการพิจารณาการเดินจาก $u$ ไปหา $v$ ใด ๆ เราสามารถพิจารณา เวลาจบ ของ $u$ และ เวลาเริ่ม เพื่อทำการหาค่า XOR ได้เนื่องจากใน Subtree ของ $u$ เมื่อ XOR ในขณะที่เป็นเวลาเริ่มและเวลาจบจะได้ค่าเป็น 0 พอดี! โดย โครงสร้างข้อมูลที่อาจใช้สำหรับปัญหานี้อาจเป็น Segment Tree หรือ Fenwick Tree ก็ได้

คำแนะนำ

ในโจทย์ข้อนี้มักจะมีปัญหาย่อยที่มีจำนวนสีน้อย ๆ ( $C \le 20$ ) เพื่อให้สามารถเขียนได้ไม่ยากนัก (สามารถสร้าง Data Structure มาไว้ก่อนหลาย ๆ อัน) ในขณะมี่ปัญหาเต็มจะมีสีจำนวนมากทำให้จำเป็นต้องเขียน Data Structure แบบ Dynamic ซึ่งอาจอาศัยความชำนาญในการเขียน

ตัวอย่างการเขียน

const int MxN = 1000010;
const int MxC = 1000010;

struct fenwick_tree {
  vector<long long> t;
  int n;
  void init(int _n) {
    n = _n + 1;
    t.assign(n, 0);
  }
  // ...
};

fenwick_tree fw[MxC];
set<int> all_colors, vertices_color[MxN];

void plant_tree(/* ... */) {
  // ...
  for(auto color: all_colors) {
    fw[color].init(vertices_color[color].size());
  }
  // ...
}

Model Solution

o67_oct_c2_goatpay Tutorial