一、基礎知識

1. 圖 & 樹

圖：網格結構
樹：層次結構
樹是一種特殊的圖
（把多叉樹當作圖看待）

樹：只要下述條件滿足兩個即可推導出是一棵樹

1. $n$ 個頂點、$n?1$ 條邊
2. 連通圖
3. 無環圖

樹的任意兩點有且僅有一條路徑。

2. 模板

2.1 建圖

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
int n,sz[MAXN];
long long ans=0;
struct Edge{int v,w;//v:邊的終點//w:邊的權值
};
vector<Edge>adj[MAXN];
void dfs(int u,int f){//f:father 防止取出的子結點和父結點重復導致地循環}
int main(){cin>>n;for(int i=1,u,v,w;i<n;i++)cin>>u>>v>>w,adj[u].push_back({v,w}),adj[v].push_back({u,w});dfs(1,0);cout<<ans;return 0;
}

sz[u]：表示以結點 $u$ 為根的子樹的結點總數
葉結點：sz[u]=1
非葉結點：sz[u]=1+sum(sz[v])（其中 $v$ 是 $u$ 的子結點）

二、簡單循環

1. 【模板】樹的路徑求和

在這個問題中，給定一個值 $s$ 和一棵樹。在樹的每個節點有一個權值，第 $i$ 個點的權值為 $a_i$，問有多少條路徑的節點權值總和為 $s$。路徑中節點的深度必須是升序的。假設節點 $1$ 是根節點，根的深度是 $0$，它的兒子節點的深度為 $1$。路徑不必一定從根節點開始。

---

遇到路徑題，優先考慮建樹。樹的結點原則：一個爸爸可以有很多孩子，但每個孩子只有一個爸爸。根據這個原則，我們可以從葉結點開始遍歷，減少時間復雜度。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
int n,s,val[MAXN],pa[MAXN];
//parent[a]: 編號為a的結點的父結點的編號
int main(){cin>>n>>s;for(int i=1;i<=n;i++)cin>>val[i];for(int i=1,u,v;i<n;i++)cin>>u>>v,pa[v]=u;long long ans=0;//自下而上搜索，時間更少for(int u=1;u<=n;u++){int sum=0,v=u;while(v!=0&&sum<s)sum+=val[v],v=pa[v];if(sum==s)ans++;}cout<<ans;return 0;
}

2. 道路修建（改）

在 W 星球上有 $n$ 個國家。為了各自國家的經濟發展，他們決定在各個國家之間建設雙向道路使得國家之間連通。但是每個國家的國王都很吝嗇，他們只愿意修建恰好 $n?1$ 條雙向道路。
每條道路的修建都要付出一定的費用，這個費用等于道路長度乘以道路兩端的國家個數之差的絕對值。由于國家的數量十分龐大，道路的建造方案有很多種，同時每種方案的修建費用難以用人工計算，國王們決定找人設計一個軟件，對于給定的建造方案，計算出所需要的費用。請你幫助國王們設計一個這樣的軟件。

---

需要計算每個結點作為根的子樹的大小時，優先考慮建圖。根據標準建圖模板，寫出如下程序。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
int n,sz[MAXN];
long long ans=0;
struct Edge{int v,w;
};
vector<Edge>adj[MAXN];
//adj[a]={b,c}表示有一條從a到b的路徑，其邊權（長度）為c
void dfs(int u,int f){sz[u]=1;for(auto[v,w]:adj[u]){if(v==f)continue;//防止遍歷的子結點是父結點陷入死循環（因為是無向圖）dfs(v,u);sz[u]+=sz[v];ans+=1ll*w*abs(n-sz[v]-sz[v]);}
}
int main(){cin>>n;for(int i=1,u,v,w;i<n;i++)cin>>u>>v>>w,adj[u].push_back({v,w}),adj[v].push_back({u,w});dfs(1,0);cout<<ans;return 0;
}

3. 聯合權值

無向連通圖 G 有 $n$ 個點，$n?1$ 條邊。點從 $1$ 到 $n$ 依次編號，編號為 $i$ 的點的權值為 $W_i$，每條邊的長度均為 $1$。圖上兩點 $(u,v)$ 的距離定義為 $u$ 點到 $v$ 點的最短距離。對于圖 G 上的點對 $(u,v)$，若它們的距離為 $2$，則它們之間會產生 $W_v\times W_u$ 的聯合權值。
請問圖 G 上所有可產生聯合權值的有序點對中，聯合權值最大的是多少？所有聯合權值之和是多少？

---

如果建樹會有太復雜的父子關系，不妨直接建圖。舉例為 $2$ 的兩個結點要么是兄弟結點，要么是爺孫結點。所以我們可以直接粗暴地寫出如下代碼：

#include<bits/stdc++.h>
using namespace std;
const int MOD=10007;
const int MAXN=2e5+8;
int n,val[MAXN];
vector<int>adj[MAXN];
int main(){cin>>n;for(int i=1,u,v;i<n;i++)cin>>u>>v,adj[u].push_back(v),adj[v].push_back(u);for(int i=1;i<=n;i++)cin>>val[i];long long mx_wt=0,sum_wt=0;for(int u=1;u<=n;u++){//遍歷第一個點ufor(int v1:adj[u])//遍歷u的所有子結點和u的父結點for(int v2:adj[u])if(v1!=v2)//遍歷所有與u互為兄弟結點或所有和u互為爺孫結點的結點mx_wt=max(mx_wt,1ll*val[v1]*val[v2]),(sum_wt+=1ll*val[v1]*val[v2])%=MOD;}cout<<mx_wt<<" "<<sum_wt;return 0;
}

但是這樣時間復雜度實在太大，考慮進行優化。不妨這么想：假如有一個結點 $u$，它的子結點有 $v_1,v_2,v_3,v_4,v_5$。我們要求的是：
1.max{vi×vj}2.Σvi×vj1.\ \text{max}\{v_i\times v_j\} \\ 2.\ \Sigma v_i\times v_j1.?max{vi?×vj?}2.?Σvi?×vj?
前提條件：$i\ne j$。

解決 $1.$ 的最優方法：找出 $v_1,v_2,v_3,v_4,v_5$ 中的最大值和次大值，相乘即可；
解決 $2.$ 的最優方法：畫出下圖。

/	$v_1$	$v_2$	$v_3$	$v_4$	$v_5$
$v_1$		要求	要求	要求	要求
$v_2$	要求		要求	要求	要求
$v_3$	要求	要求		要求	要求
$v_4$	要求	要求	要求		要求
$v_5$	要求	要求	要求	要求

然后把所有“要求”的值進行求和。不妨用容斥原理：
$$(v_1+v_2+v_3+v_4+v_5{)}^2?(v_1^2+v_2^2+v_3^2+v_4^2+v_5^2)$$

于是有了如下程序：

#include<bits/stdc++.h>
using namespace std;
const int MOD=10007;
const int MAXN=2e5+8;
int n,s,val[MAXN];
vector<int>adj[MAXN];
int main(){cin>>n;for(int i=1,u,v;i<n;i++)cin>>u>>v,adj[u].push_back(v),adj[v].push_back(u);for(int i=1;i<=n;i++)cin>>val[i];long long mx_wt=0,sum_wt=0;for(int u=1;u<=n;u++){long long mx_val=0,sub_val=0,sum_val=0,sum_val2=0;for(int v:adj[u]){if(val[v]>=mx_val)sub_val=mx_val,mx_val=val[v];else if(val[v]>=sub_val)sub_val=val[v];sum_val+=val[v];sum_val2+=1ll*val[v]*val[v];}mx_wt=max(mx_wt,mx_val*sub_val);sum_wt=(sum_wt+sum_val*sum_val-sum_val2)%MOD;}cout<<mx_wt<<" "<<sum_wt;return 0;
}

mx_val：最大權值
sub_wal：次大權值
sum_val：權值的和
sum_val2：權值的平方的和

4. 毛毛蟲樹

毛毛蟲通常由身體和細小的足組成，所有的足都和毛毛蟲的身體直接相連。
如果一個無向圖滿足以下性質，我們稱這個圖叫做毛毛蟲圖（Caterpillar）：
1、圖中沒有環，并且圖上所有節點都相互連通。
2、在圖中能找到一條路徑，使得所有節點不是在路徑上，就是與路徑上的節點有直接連邊。

根據上述內容，我們可以寫出一個判斷程序：

1. 檢查這個圖是不是一棵樹（滿足 $n$ 個結點 $n?1$ 條邊）
2. 檢查每個點是否最多只連接了兩個身體結點（即身體不能分叉，如下）

3. 遍歷一遍所有結點，檢查所有結點是否相互連通（每個結點是否都被遍歷到了）

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
int n,m;
vector<int>adj[MAXN];
bool is_ctp,vis[MAXN];
void dfs(int u){int cnt=0;//統計身體結點個數for(int v:adj[u]){cnt+=(adj[v].size()>1);//父結點的計算也包含在內if(!vis[v])vis[v]=true,dfs(v);}//每個結點最多連接兩個身體結點if(cnt>2)is_ctp=false;//連了超過兩個身子，說明u是身體結點，相當于一個身體結點至少有三個子結點（而這個三個點又都是身體結點）
}
int main(){int T=0;while(cin>>n&&n){T++;memset(vis,false,sizeof(vis));for(int u=1;u<=n;u++)adj[u].clear();cin>>m;for(int i=1,u,v;i<=m;i++)cin>>u>>v,adj[u].push_back(v),adj[v].push_back(u);is_ctp=(n-m==1);if(!is_ctp)cout<<"Graph "<<T<<" is not a caterpillar.\n";vis[1]=true,dfs(1);for(int u=1;u<=n;u++)is_ctp&=vis[u];cout<<"Graph "<<T<<(is_ctp?" is":" is not")<<" a caterpillar.\n";}return 0;
}

三、自頂向下/自底向上

1. 醫療中心

在一個偏遠的山區，政府需要在村莊之間選取建造一個醫療中心。山區的村莊由一張樹結構的地圖表示，其中每個村莊的居民數量（人口數）標注在圈內，而每個村莊的編號寫在圈邊上。村莊之間的道路恰好能連通所有村莊且長度固定為 $1$。
為了方便居民就醫，規劃團隊希望醫療中心的位置能夠使得所有居民到醫療中心的總路程最短。具體來說，如果醫療中心建在某個村莊處，每個居民到醫療中心的距離是他們所在村莊與醫療中心所在村莊的路徑長度。最終，需要在地圖上找到一個最佳的村莊設立醫療中心，使得所有居民到達醫療中心的總距離最小。

---

這是一道經典的樹形 dp 問題，我們考慮兩種方法：自頂向下地推深度、自底向上遞推結點和。

• 自頂向下的方法：只需要在 dfs 函數的第一行遞推，第二行更新結果，自己的子結點直接無腦遞歸，不用任何操作；
• 自底向上的方法：dfs 函數的第一行先把自己的一部分推出來。遍歷的時候，一開始就遞歸，而遞歸后子結點對應的值 sum[v] 已經推導完畢，且我們認為是正確的，然后根據它來更新 sum[u] 的值和最終答案。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+8;
vector<int>adj[MAXN];
long long res,sum[MAXN];
int n,val[MAXN],dep[MAXN];
// void dfs(int u,int f){//自頂向下地推深度
//     dep[u]=dep[f]+1;
//     res+=1ll*val[u]*(dep[u]-1);
//     for(int v:adj[u])
//         if(v!=f)
//             dfs(v,u);
// }
void dfs(int u,int f){//自底向上遞推結點和sum[u]=val[u];for(int v:adj[u]){if(v==f)continue;dfs(v,u);sum[u]+=sum[v];res+=sum[v];}
}
int main(){cin>>n;for(int u=1,f;u<=n;u++){cin>>val[u]>>f;if(f)adj[f].push_back(u),adj[u].push_back(f);}long long ans=1e18;for(int r=1;r<=n;r++)res=0,dfs(r,0),ans=min(ans,res);cout<<ans;return 0;
}

2. 【模板】樹的直徑

FJ 希望他的奶牛們加強鍛煉，于是決定舉辦一場別開生面的奶牛馬拉松。馬拉松的路線圖會包含一系列的農場，以及連接這些農場的雙向道路。FJ 保證任意兩個農場之間有且僅有一條路徑。鑒于 FJ 希望奶牛們得到盡可能多的鍛煉，他想請你幫他找出最長的馬拉松路線，即在地圖中找出相距最遠的兩個農場（兩個農場之間的距離即這兩個農場之間路徑所包含的道路總長）之間的路線。

---

經典的樹的直徑求解問題。模板需要熟練背誦。

【推薦】方法 1：樹形 dp

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e4+8;
struct Edge{int v,w;};
int n,m,ans,dp[MAXN];
vector<Edge>adj[MAXN];
void dfs(int u,int f){//自底向上for(auto[v,w]:adj[u]){if(v==f)continue;dfs(v,u);ans=max(ans,dp[u]+(dp[v]+w));//dp[u]+(dp[v]+w)表示以u為轉折點連接其兩個子樹的最長路徑dp[u]=max(dp[u],dp[v]+w);//dp[v]+w表示從u經過邊(u,v)到v子樹的最長路徑}
}
int main(){cin>>n>>m;char ch;for(int i=1,x,y,d;i<=m;i++){cin>>x>>y>>d>>ch;adj[x].push_back({y,d});adj[y].push_back({x,d});}dfs(1,0);cout<<ans;return 0;
}

方法 2：兩次 dfs

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e4+8;
struct Edge{int v,w;};
int n,m,dis[MAXN];
vector<Edge>adj[MAXN];
void dfs(int u,int f){for(auto[v,w]:adj[u])if(v!=f)dis[v]=dis[u]+w,dfs(v,u);
}
int main(){cin>>n>>m;char ch;for(int i=1,x,y,d;i<=m;i++){cin>>x>>y>>d>>ch;adj[x].push_back({y,d});adj[y].push_back({x,d});}dfs(1,0);int s=1;for(int i=2;i<=n;i++)if(dis[i]>dis[s])s=i;dis[s]=0,dfs(s,0);int t=1;for(int i=2;i<=n;i++)if(dis[i]>dis[t])t=i;cout<<dis[t];return 0;
}

3. 【模板】最大子樹和

小明對數學飽有興趣，并且是個勤奮好學的學生，總是在課后留在教室向老師請教一些問題。一天他早晨騎車去上課，路上見到一個老伯正在修剪花花草草，頓時想到了一個有關修剪花卉的問題。于是當日課后，小明就向老師提出了這個問題：
一株奇怪的花卉，上面共連有 $N$ 朵花，共有 $N?1$ 條枝干將花兒連在一起，并且未修剪時每朵花都不是孤立的。每朵花都有一個“美麗指數”，該數越大說明這朵花越漂亮，也有“美麗指數”為負數的，說明這朵花看著都讓人惡心。所謂“修剪”，意為：去掉其中的一條枝條，這樣一株花就成了兩株，扔掉其中一株。經過一系列“修剪“之后，還剩下最后一株花（也可能是一朵）。老師的任務就是：通過一系列“修剪”（也可以什么“修剪”都不進行），使剩下的那株（那朵）花卉上所有花朵的“美麗指數”之和最大。
老師想了一會兒，給出了正解。小明見問題被輕易攻破，相當不爽，于是又拿來問你。

---

一道模板題，和最大子段和問題一模一樣，只不過是在樹上。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1.6e4+8;
vector<int>adj[MAXN];
int n,val[MAXN],dp[MAXN];
void dfs(int u,int f){//自底向上dp[u]=val[u];for(int v:adj[u])if(v!=f)dfs(v,u),dp[u]+=max(dp[v],0);
}
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>val[i];for(int i=1,u,v;i<n;i++)cin>>u>>v,adj[u].push_back(v),adj[v].push_back(u);dfs(1,0);int ans=-1e9;for(int u=1;u<=n;u++)ans=max(ans,dp[u]);cout<<ans;return 0;
}

4. 信號放大器

題目傳送門

---

啊？這道題配當藍題嗎？啊？？？？？

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e4+8;
int n,ra,ans,dp[MAXN];
struct Edge{int v,w;};
vector<Edge>adj[MAXN];
void dfs(int u,int f,int dis){for(auto[v,w]:adj[u])if(v!=f){dfs(v,u,w);dp[u]=max(dp[u],dp[v]+w);}if(dp[u]>=ra)ans=1e9;//如果當前結點的最大衰減路徑超過信號強度，說明無法覆蓋if(f!=0&&dis+dp[u]>=ra)ans++,dp[u]=0;//如果不是根結點，且從父結點到這里的衰減+當前子樹最大衰減>=信號強度，//說明需要在當前結點安裝放大器，同時重置當前路徑的衰減計算
}
int main(){cin>>n;for(int u=1,k;u<=n;u++){cin>>k;for(int j=1,v,w;j<=k;j++)cin>>v>>w,adj[u].push_back({v,w});}cin>>ra;dfs(1,0,0);if(ans>=1e9)return cout<<"No solution.",0;cout<<ans;return 0;
}