solution

Khử biểu thức con chung (Common Subexpression Elimination – CSE) là một phép tối ưu hóa quan trọng trên cây cú pháp AST: nếu hai cây con của AST có cấu trúc và nội dung giống hệt nhau, trình biên dịch chỉ cần tính một lần và dùng chung kết quả, thay vì tính lặp lại nhiều lần.

Cho một biểu thức tiền tố (toán tử $\{+, -, *, /, \wedge\}$, toán hạng là chữ cái thường hoặc số nguyên không âm). Với mỗi nút của cây (kể cả lá), gọi biểu diễn tiền tố chuẩn tắc của cây con gốc tại nút đó là chuỗi token thu được khi in cây con này ra dạng tiền tố (giữ nguyên thứ tự trái phải, không áp dụng tính giao hoán — ví dụ + a b và + b a được coi là khác nhau).

Hai cây con được gọi là trùng nhau khi và chỉ khi biểu diễn tiền tố chuẩn tắc của chúng là hai chuỗi giống hệt nhau.

Hãy tính:

• total: tổng số nút trong cây gốc (đếm mọi nút, kể cả các cây con trùng nhau xuất hiện ở nhiều vị trí khác nhau) — đây chính là số token trong biểu thức.
• distinct: số chuỗi biểu diễn tiền tố chuẩn tắc khác nhau xuất hiện trong tập tất cả cây con của cây (nếu dùng CSE, mỗi cây con trùng nhau chỉ cần tính/lưu một lần).
• saved = total - distinct: số nút có thể tiết kiệm được nếu áp dụng CSE triệt để.

Ví dụ: với * + a b + a b, cây con + a b xuất hiện $2$ lần (giống hệt nhau), hai lá a và hai lá b cũng lặp lại. total = 7 (7 token), các chuỗi phân biệt là {"* + a b + a b", "+ a b", "a", "b"} nên distinct = 4, saved = 3.