發表新討論
#37590: 解題報告


dfd8282@gmail.com (fishhh)

學校 : 嘉義市私立嘉華高級中學
編號 : 99760
來源 : [140.114.216.99]
最後登入時間 ：
2024-10-27 14:56:56
b218. 3. 找關鍵人物 -- 97學年度全國資訊學科能力競賽 | From: [114.40.204.10] | 發表日期 : 2023-09-18 00:15

這個技巧應該叫做換根? rerooting (這是不重要啦w

這題算是這個技巧的裸題了 學過的人 甚至沒學過有感覺應該都可以直接寫出來

主要就 DFS 兩次

第一次：先任選一個節點當作根(我都選1 反正沒差) 直接從根開始 DFS 很簡單 只要維護每個節點為子樹的大小就好

第二次：
可以知道會經過點 1 的路徑總和就是他的每個子樹兩兩大小乘積總和
其他點也是，但問題就是每個點可以知道所有從自己往下的所有子樹大小 但無法得知從上面來的
(例如範例 1 把 1 當作根後
4 這個點可以知道兩棵子樹 分別是 8 以及 5 7 4
所以我們也把 3 當成一棵子樹 但問題就是不知道它的大小
下面直接附程式
 
 
// 計算每個節點子樹大小的DFS
void dfs1(int now,int from){
    sz[now] = 1;
    for(int i:edge[now]){
        if(i==from)continue;
        dfs1(i,now);
        sz[now]+=sz[i];
    }
    return ;
}
 
 
// 計算每個點作為根的DFS
其中 sf 這個傳入就是 now 往回走到 from 節點的子樹大小
// vector 就只是把所有子樹的大小紀錄起來 最後 O(n^2) 計算兩兩乘積和
void dfs2(int now,int from,int sf){
    int res = 0;
    vi v;
    for(int i:edge[now]){
        if(i==from)continue;
        if(sz[i])v.pb(sz[i]);
    }
    if(sf)v.pb(sf);
    for(int i=0;i<v.size();i++){
        for(int j=i+1;j<v.size();j++){
            res+=v[i]*v[j];
        }
    }
    ans[now] = res;
    for(int i:edge[now]){
        if(i==from)continue;
        dfs2(i,now,sz[now]-sz[i]+sf);
    }
    return ;
}
 
ZeroJudge Forum