Mô tả bài toán

===========

Mô tả

Cho một cây có n đỉnh và m chuỗi trên cây, yêu cầu là đếm có bao nhiêu cặp chuỗi có ít nhất một điểm chung.

Input

Dòng đầu tiên chứa hai số nguyên dương n, m. Dòng thứ 2 đến dòng thứ n, mỗi dòng chứa hai số nguyên s, t, biểu thị có một cạnh nối s và t.

Tiếp theo m dòng, mỗi dòng chứa hai số nguyên a, b, biểu thị một chuỗi có đầu mút là a và b (đầu mút có thể giống nhau).

Output

Một dòng chứa một số nguyên, biểu thị đáp án.

Ví dụ đầu vào

5 3

1 2

1 3

2 4

2 5

4 5

1 4

3 5

Ví dụ đầu ra

3

Gợi ý

Với 30% dữ liệu, $n,m \leq 100$

Với 50% dữ liệu, $n,m \leq 2000$

Với thêm 20% dữ liệu, các cặp $s,t$ đọc vào thỏa mãn $t=s+1$

Với 100% dữ liệu, $1 \leq n,m \leq 100000$

Giới thời gian: $1s$ Giới hạn bộ nhớ: $512MB$

Phân tích bài toán

Yếu tố quan trọng của bài toán này là phương pháp xác định hai chuỗi có giao nhau hay không. Trước hết, chúng ta cần phân tích các trường hợp hai chuỗi giao nhau. Như hình vẽ dưới đây:

(Hình A: Chuỗi $S1-T1$ và $S2-T2$ có một điểm giao là O)

(Hình B: Chuỗi $S1-T1$ và $S2-T2$ có hai hoặc nhiều điểm giao)

Từ hình trên, chúng ta có thể kết luận rằng hai chuỗi giao nhau khi và chỉ khi một trong hai điểm đầu mút của chuỗi này có LCA nằm trên chuỗi kia.

Bây giờ chúng ta cần phân loại các trường hợp. Với trường hợp đầu tiên, chúng ta chỉ cần đếm xem có bao nhiêu chuỗi có LCA tại một điểm nào đó, đặt $cnt_i$ là số chuỗi có LCA tại điểm x. Khi đó, nếu $cnt_i>1$, điều này có nghĩa là có nhiều chuỗi đi qua điểm này, tức là có $n \times (n - 1) \div 2$ cặp chuỗi giao nhau. Quá trình này được viết thành code như sau:

for(int i=1;i<=n;i++) ketqua+=cnt[i]*(cnt[i]-1)/2;<br></br>

Với trường hợp thứ hai, phức tạp hơn một chút. Chúng ta cần xem xét một chuỗi có bao nhiêu LCA của các chuỗi khác nằm trên nó. Chúng ta cần một mảng tổng tiền tố $prefix$, có công thức truy hồi là $prefix_v = prefix_u + cnt_v$ (v là con của u), cuối cùng để tính tổng số LCA trên mỗi chuỗi, chúng ta chỉ cần tính $prefix_u + prefix_v - 2 \times prefix_lca(u,v)$ (u, v là hai đầu mút của chuỗi). Quá trình này được viết thành code như sau:

void giaiQuyet(int nut, cha)
{
    prefix[nut]=prefix[cha]+cnt[nut]; //truy hồi
    for(auto &con: danhSachKe[nut]) //duyệt qua các con
        if(con!=cha)
            giaiQuyet(con,nut);
}

for(int i=1;i<=m;i++)    ketqua+=prefix[chuoi[i].dau]+prefix[chuoi[i].cuoi]-2*prefix[chuoi[i].lca];

Cuối cùng, chỉ cần in ra giá trị của ketqua là xong.

Code hoàn chỉnh

Một bài giải không có code thì không phải là bài giải tốt.

 1 #include <bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 int n,m,ketqua,sau[100005],cha[100005][20],prefix[100005],cnt[100005];
 5 vector<int> danhSachKe[100005]; //dùng vector lưu đồ thị, kết hợp với C++11 ngon hơn 
 6 struct Chuoi
 7 {
 8     int dau,cuoi; //đầu và cuối của chuỗi 
 9     int lca; //LCA của hai đầu mút 
10 }chuoi[100005];
11 void dfs(int nut, cha) //tiền xử lý LCA 
12 {
13     sau[nut]=sau[cha]+1;
14     cha[nut][0]=cha;
15     for(int i=1;(1<<i)<=sau[nut];i++)
16         cha[nut][i]=cha[cha[nut][i-1]][i-1];
17     for(auto &con: danhSachKe[nut])
18         if(con!=cha)
19             dfs(con,nut);
20 }
21 int lca(int a,int b) //tìm tổ tiên chung gần nhất 
22 {
23     if(sau[a]<sau[b])    swap(a,b);
24     for(int i=17;i>=0;i--)
25     {
26         if(sau[cha[a][i]]>=sau[b])
27             a=cha[a][i];
28         if(a==b)    return a;
29     }
30     for(int i=17;i>=0;i--)
31         if(cha[a][i]!=cha[b][i])
32             a=cha[a][i],b=cha[b][i];
33     return cha[a][0];
34 }
35 void giaiQuyet(int nut, cha) //tính mảng tổng tiền tố 
36 {
37     prefix[nut]=prefix[cha]+cnt[nut];
38     for(auto &con: danhSachKe[nut])
39         if(con!=cha)
40             giaiQuyet(con,nut);
41 }
42 signed main()
43 {
44     scanf("%lld%lld",&n,&m); //nhập dữ liệu 
45     for(int i=1;i<n;i++)
46     {
47         int u,v;
48         scanf("%lld%lld",&u,&v);
49         danhSachKe[u].push_back(v);
50         danhSachKe[v].push_back(u);
51     }
52     dfs(1,0);
53     for(int i=1;i<=m;i++)
54     {
55         scanf("%lld%lld",&chuoi[i].dau,&chuoi[i].cuoi);
56         chuoi[i].lca=lca(chuoi[i].dau,chuoi[i].cuoi);
57     }
58     for(int i=1;i<=m;i++)    cnt[chuoi[i].lca]++; //đếm cnt 
59     giaiQuyet(1,0);
60     for(int i=1;i<=n;i++)    ketqua+=cnt[i]*(cnt[i]-1)/2; //tính trường hợp 1 
61     for(int i=1;i<=m;i++)    ketqua+=prefix[chuoi[i].dau]+prefix[chuoi[i].cuoi]-2*prefix[chuoi[i].lca]; //tính trường hợp 2 
62     printf("%lld",ketqua);
63     while(1); //không có công cụ chống đạo văn thì không phải là bài giải tốt... 
64     return 0;
65 }