---

前言

不會做，全靠靈神的視頻講解

2867.統計樹中的合法路徑數目

思路

考慮質數節點，每個質數節點應該都有屬于它自己的多個連通塊，而每個連通塊中存在的非質數路徑那么就可以形成一條合法路徑

所以我們需要去統計一個質數的連通塊中有多少非質數的連通情況，最后結果相加即可

確定1e5中的質數

對于一個質數，其的倍數一定不是質數

    void checknp(bool* np){np[1] = true;for(int i = 2;i*i<MX+1;i++){for(j = i*i ;j <MX+1;j+=i){if(!np[i]){np[j] = true;}}}}

統計每個點的連接情況

根據傳入參數edgs數組，可以得到每個點與哪些點連接

        vector<vector<int>> connect(n+1);for(auto edge : edges){connect[edge[0]].push_back(edge[1]);connect[edge[1]].push_back(edge[0]);}

開始對質數點進行處理

我們需要用到記憶化搜索的技巧。當我們對一個非質數與哪些非質數連接情況進行討論后，我們可以將結果存儲，如果后面有質數節點也與該非質數節點連接，那么就可以直接使用了。

//記錄返回值 和 記憶化存儲非質數節點與多少個非質數節點連接
long long res = 0;
vector<int> mem(n+1);
for(int i = 1;i<n+1;i++)
{//如果是非質數，就可以跳過，因為我們只考慮質數的連通if(np[i]) continue;//記錄連通數int sum = 0;//對i的連通點進行處理結果for(int j : connect[i]){//只考慮非質數的情況if(!np[j]) continue;//如果沒有被搜索過if(mem[j] == 0){//存儲相互連接節點的數組清空nodes.clear();checknodes(j,-1,connect);//對于nodes數組里面的所有點，其連通點的個數都是nodes數組的長度for(int k : nodes){mem[k] = nodes.size();}}//計算結果，質數i下面的j連通塊res += mem[j] * sum;sum += mem[j];}//以質數為頭的結果res += sum;
}

完整代碼

const int MX = 1e5;
class Solution {
private:bool np[MX+1];vector<int> nodes;
public:void checknp(bool* np){np[1] = true;for(int i = 2;i*i<MX+1;i++){for(int j = i*i ;j <MX+1;j+=i){if(!np[i]){np[j] = true;}}}}void checknodes(int x,int fa,vector<vector<int>>& connect){nodes.push_back(x);for(int y:connect[x]){if(y!=fa&&np[y]){checknodes(y,x,connect);}}}
public:long long countPaths(int n, vector<vector<int>>& edges) {checknp(np);vector<vector<int>> connect(n+1);for(auto edge : edges){connect[edge[0]].push_back(edge[1]);connect[edge[1]].push_back(edge[0]);}//結果long long res = 0;//記憶化搜索vector<int> mem(n+1);for(int i = 1;i<n+1;i++){if(np[i]) continue;//記錄當前節點的連接數int sum = 0;for(int j : connect[i]){if(!np[j]) continue;//如果沒被遍歷過if(mem[j] == 0){nodes.clear();checknodes(j,-1,connect);//修改記憶存儲結果for(int k : nodes){mem[k] = nodes.size();}}//統計該連通塊對結果的影響res += mem[j]*sum;sum += mem[j];}//已質數節點為頭的情況res += sum;}return res;}
};

2673.使二叉樹所有路徑值相等的最小代價

思路

從葉子節點開始，計算根節點到該葉子節點的路徑和，然后修改其中一個葉子節點使得和相等，由于只能增加，所以向大值修改。
修改完成后將該和返回給葉子節點的父節點，然后比較同一層級的父節點的和，進行修改。
逐步返回直到根節點

完整代碼

對于滿二叉樹，父節點和左右子結點在數組中存在一個關系。

class Solution {
public:int minIncrements(int n, vector<int>& cost) {//統計每個節點的路徑和for(int i = 2;i<n+1;i++){cost[i-1] += cost[i/2-1];}//更新結果int res = 0;for(int i = n/2;i>0;i--){res += abs(cost[2*i]-cost[2*i-1]);cost[i-1] = max(cost[2*i],cost[2*i-1]);}return res;}
};

2581.統計可能的樹根數目

思路

還不是很明白
我們假設以0為根的正確猜測是cnt0，那調換到以1為根，那么cnt1的值
首先需要減去guesses數組[0,1]的數量，再加上[1,0]的數量，因為[u,v]表示u是v的父節點。
其余調換類似。

建立連通關系

vector<vector<int>> g(edges.size() + 1);
for (auto &e : edges) 
{int x = e[0], y = e[1];g[x].push_back(y);g[y].push_back(x);
}

將猜測數組變為哈希表，方便查詢

unordered_set<LL> s;
for (auto &e : guesses) 
{ // guesses 轉成哈希表s.insert((LL) e[0] << 32 | e[1]); // 兩個 4 字節數壓縮成一個 8 字節數
}

利用dfs初始化根為0的猜測正確數量

int ans = 0, cnt0 = 0;
function<void(int, int)> dfs = [&](int x, int fa) 
{//y與x連通for (int y : g[x]){//y不是父節點，防止反向計算if (y != fa) {//[x,y]如果存在哈希表中，表面以0為根的結果猜測正確+1cnt0 += s.count((LL) x << 32 | y); // 以 0 為根時，猜對了//以當前節點為父節點搜索子結點dfs(y, x);}}
};
dfs(0, -1);

統計完整的結果

//計算以x為根的cnt
function<void(int, int, int)> reroot = [&](int x, int fa, int cnt) 
{ans += cnt >= k; // 此時 cnt 就是以 x 為根時的猜對次數for (int y : g[x]) {if (y != fa) {//從0開始，變換根為0的連通節點，在變換為連通節點的連通節點reroot(y, x, cnt- s.count((LL) x << 32 | y)   // 原來是對的，現在錯了+ s.count((LL) y << 32 | x)); // 原來是錯的，現在對了}}
};
reroot(0, -1, cnt0);