題解/算法 {2867. 统计树中的合法路径数目}

題解/算法 {2867. 统计树中的合法路径数目}
@LINK: https://leetcode.cn/problems/count-valid-paths-in-a-tree/;

令路徑中唯一的質數為x, 則該路徑一定形如pre-x-suf 或x-?(即x為端點);

{ 錯誤

以1節點為根, 通過換根DP, 你可以得到Down[x]: x為質數 且他往下走 且不經過質數的路徑個數(也就是節點額數); Up[x]: 往上走;
則形如pre-x-suf的路徑個數為 Up[x] * Down[x], 形如x-?的路徑個數為Up[x] + Down[x];

其實這是錯誤的…
因為pre,suf可以同時存在於Down裡, 比如x往下有a,b兩個兒子, 那麼你沒有記錄形如?-a-x-b-?的路徑 (當然?-a-x-a-?是非法的);

因此 你需要繼續對Down做劃分;
其實這個題 跟Up/Down無關, 其實他的本質是這樣的: 對於質數x 他有一個int C[K]序列, 表示他有K個分支(無所謂兒子/父親) 每個分支的C[i]表示 x-i-?(i,?都不為質數)的方案數;
. 因此答案為: x-?路徑個數為sum( C[K]), pre-x-suf的個數為(從任意兩個C[i],C[j]裡選擇兩個數的方案);

}

因此關鍵是得到這個C[K]序列, 此時有2個辦法: {1:[換根DP]; 2:[連通塊(記憶化DFS)]};
這裡講下第二種方法, 對著一棵樹 你把所有的質數節點都給去掉後 他就變成了若干個連通塊, 那麼對於某個質數節點x 他的C[K]值 就對應 x節點相鄰的 K個連通塊的 大小 (這是無根樹 無所謂兒子/父親); 因此遍歷所有質數節點x的所有非質數鄰接點y 使用記憶化DFS 獲取y所在連通塊的大小;

此時還有個問題, 這個C[K] 他是$O(N)$級別的, 如果你通過N^2級別時間 來獲取他的答案 會超時的;
因此 需要優化 這也是個難點; C1, C2, ...., CK, 對於形如x-?的路徑 答案是sum( C1+...+CK) 這是O(1)的; 關鍵是求形如pre-x-suf的路徑 要是直接Ci-x-Cj 這是N^2會超時, 我們劃分為C1-x-C2, {C1|C2}-x-C3, {C1|C2|C3}-x-C4, ... 即對於Ci 令s= C1+C2+...+C[i-1] 則該項的答案為s * Ci;
代碼如下:

for( x : 所有質數節點){
    long long s = 0;
    for( c : C[x]){
        ANS += s * c;
        ANS += c;
        s += s;
    }
}
1
2
3
4
5
6
7
8