这两道题都是用简单dfs解的，主要是熟悉回溯过程就能做，据说用bfs也能做
道路修建（HYSBZ - 2435）
在 W 星球上有 n 个国家。为了各自国家的经济发展，他们决定在各个国家
之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿意修建恰好n – 1条双向道路。 每条道路的修建都要付出一定的费用， 这个费用等于道路长度乘以道路两端的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有 2 个、4个国家，如果该道路长度为 1，则费用为1×|2 – 4|=2。图中圆圈里的数字表示国家的编号。
由于国家的数量十分庞大，道路的建造方案有很多种，同时每种方案的修建
费用难以用人工计算，国王们决定找人设计一个软件，对于给定的建造方案，计
算出所需要的费用。请你帮助国王们设计一个这样的软件。
Input
输入的第一行包含一个整数n，表示 W 星球上的国家的数量，国家从 1到n
编号。接下来 n – 1行描述道路建设情况，其中第 i 行包含三个整数ai、bi和ci，表
示第i 条双向道路修建在 ai与bi两个国家之间，长度为ci。
Output
输出一个整数，表示修建所有道路所需要的总费用。
Sample Input
6
1 2 1
1 3 1
1 4 2
6 3 1 5 2 1
Sample Output
20
Hint
n = 1,000,000 1≤ai, bi≤n
0 ≤ci≤ 10^6
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <queue>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
typedef long long LL;
#define Fil(Array, len, num) fill(Array, Array + len, num)
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const double PI = 3.1415926;
const double E = 2.1718281828;
const int MAXN = 1000005;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
struct Edge
{
int to, w, next;
}edge[MAXN << 1];
int head[MAXN << 1], cnt, vis[MAXN];
void Add(int a, int b, int c)
{
edge[++cnt].to = b;
edge[cnt].w = c;
edge[cnt].next = head[a];
head[a] = cnt;
}
int n, num[MAXN];
LL ans;
void dfs(int s)
{
num[s] = 1;
for(int i = head[s];i != -1;i = edge[i].next)
{
if(!vis[edge[i].to])
{
vis[edge[i].to] = 1;
dfs(edge[i].to);
num[s] += num[edge[i].to];
ans += (LL)abs(n - 2 * num[edge[i].to]) * edge[i].w;//这里要注意是num[edge[i].to]
}
}
}
int main()
{
scanf("%d", &n);
Fil(head, MAXN, -1);
int a, b, c;
for(int i = 1;i < n;++i)
{
scanf("%d%d%d", &a, &b, &c);
Add(a, b, c);
Add(b, a, c);
}
vis[1] = 1;
dfs(1);
cout << ans << endl;
return 0;
}
UVALive - 6436
题目里面的图拉不下来，就自己看题吧
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <queue>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
typedef long long LL;
#define Fil(Array, len, num) fill(Array, Array + len, num)
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const double PI = 3.1415926;
const double E = 2.1718281828;
const int MAXN = 1000005;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
vector<int> mp[MAXN];
int num[MAXN], n;
LL ans;
void dfs(int s, int fa)
{
num[s] = 1;
int len = mp[s].size();
LL t = 0;
for(int i = 0;i < len;++i)
{
if(mp[s][i] == fa)
continue;
dfs(mp[s][i], s);
num[s] += num[mp[s][i]];
// 这里是算该点之后的所有点，然后算忙碌度
t += (LL)((n - num[mp[s][i]] - 1) * num[mp[s][i]]);
// cout << s << " " << mp[s][i] << " " << t << " " << num[mp[s][i]] << endl;
}
// 这里还要算这个点前面的有几个点，加上忙碌度，算出来每两个点都算了两次
t += (LL)(n - num[s]) * (num[s] - 1);
ans = max(ans, t);
}
int main()
{
int T;
scanf("%d", &T);
for(int cas = 1;cas <= T;++cas)
{
for(int i = 0;i < MAXN;++i)
mp[i].clear();
ans = 0;
scanf("%d", &n);
for(int i = 1;i < n;++i)
{
int a, b;
scanf("%d%d", &a, &b);
mp[a].push_back(b);
mp[b].push_back(a);
}
dfs(1, -1);
printf("Case #%d: %lld\n", cas, ans / 2);
}
return 0;
}