一、基础知识

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;
}