樹的最長路徑

給定一棵樹，樹中包含?n?個結(jié)點（編號1~n）和?n?1 條無向邊，每條邊都有一個權(quán)值。

現(xiàn)在請你找到樹中的一條最長路徑。

換句話說，要找到一條路徑，使得使得路徑兩端的點的距離最遠(yuǎn)。

注意：路徑中可以只包含一個點。

輸入格式

第一行包含整數(shù)?n。

接下來?n?1 行，每行包含三個整數(shù)?ai,bi,ci，表示點?ai 和?bi 之間存在一條權(quán)值為?ci 的邊。

輸出格式

輸出一個整數(shù)，表示樹的最長路徑的長度。

數(shù)據(jù)范圍

1≤n≤10000,
1≤ai,bi≤n,
?1e5≤ci≤1e5

輸入樣例：

6
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7

輸出樣例：

22

?邊權(quán)不為負(fù)可以用兩次dfs，邊權(quán)有負(fù)就要用這種了

一個點選兩個能走得貢獻(xiàn)最大的孩子，相加就是能搭在這個點上最長的直徑，所有點跑一遍，找最長的那個就行

理論上一個直徑上每個點算出來的值都不一樣，因為dfs得有個順序，都是父親向孩子走得，但每條直徑都一定會被算到。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 20010;int pos, n;
int h[N], e[N], w[N], ne[N], idx;
int ans;void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}int dfs(int u, int father)
{int dist = 0;int d1 = 0, d2 = 0;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == father)continue;int d = dfs(j, u) + w[i];dist = max(dist, d);if(d > d1)d2 = d1, d1 = d;else if(d > d2)d2 = d;}ans = max(ans, d1 + d2);return dist;
}int main()
{IOScin >> n;memset(h, -1, sizeof h);for(int i = 1; i < n; i ++){int a, b, c;cin >> a >> b >> c;add(a, b, c);add(b, a, c);}dfs(1, -1);cout << ans;return 0;
}

樹的中心

給定一棵樹，樹中包含?n個結(jié)點（編號1~n）和?n?1 條無向邊，每條邊都有一個權(quán)值。

請你在樹中找到一個點，使得該點到樹中其他結(jié)點的最遠(yuǎn)距離最近。

輸入格式

第一行包含整數(shù)?n。

接下來?n?1 行，每行包含三個整數(shù)?ai,bi,ci，表示點?ai?和?bi?之間存在一條權(quán)值為?ci?的邊。

輸出格式

輸出一個整數(shù)，表示所求點到樹中其他結(jié)點的最遠(yuǎn)距離。

數(shù)據(jù)范圍

1≤n≤10000,
1≤ai,bi≤n,
1≤ci≤1e5

輸入樣例：

5 
2 1 1 
3 2 1 
4 3 1 
5 1 1

輸出樣例：

2

?可以延續(xù)上一題的思路，嘗試枚舉一下每個點

最遠(yuǎn)距離除了往下走的還有一條往上走的，要在兩者中取一個最大值

dist數(shù)組存往下走的最大值，up數(shù)組存往上走的最大值

第一次dfs可以求出dist數(shù)組的每個值

然后第二次dfs可以用dist數(shù)組的值退出來up的值，根節(jié)點up為0，然后就可以按dfs順序遞推出來孩子的up的值了。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 20010;int pos, n;
int h[N], e[N], w[N], ne[N], idx;
int dist[N], up[N];
int ans = 2e9;void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}int dfs(int u, int father)
{int res = 0;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == father)continue;int d = dfs(j, u) + w[i];res = max(res, d);}dist[u] = res;return res;
}void dfs1(int u, int father)
{int d1 = 0, d2 = 0;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == father)continue;int d = dist[j] + w[i];if(d > d1)d2 = d1, d1 = d;else if(d > d2)d2 = d;}if(up[u] > d1)d2 = d1, d1 = up[u];else if(up[u] > d2)d2 = up[u];for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == father)continue;int res;if(dist[j] + w[i] == d1)res = d2;else res = d1;up[j] = res + w[i];int tmp = max(up[j], dist[j]);ans = min(ans, tmp);dfs1(j, u);}
}int main()
{IOScin >> n;memset(h, -1, sizeof h);for(int i = 1; i < n; i ++){int a, b, c;cin >> a >> b >> c;add(a, b, c);add(b, a, c);}dfs(1, -1);dfs1(1, -1);ans = min(ans, dist[1]);cout << ans;return 0;
}

數(shù)字轉(zhuǎn)換

如果一個數(shù)?x?的約數(shù)之和?y（不包括他本身）比他本身小，那么?x?可以變成?y，y?也可以變成?x。

例如，4?可以變?yōu)?3，1?可以變?yōu)?7。

限定所有數(shù)字變換在不超過?n?的正整數(shù)范圍內(nèi)進(jìn)行，求不斷進(jìn)行數(shù)字變換且不出現(xiàn)重復(fù)數(shù)字的最多變換步數(shù)。

輸入格式

輸入一個正整數(shù)?n。

輸出格式

輸出不斷進(jìn)行數(shù)字變換且不出現(xiàn)重復(fù)數(shù)字的最多變換步數(shù)。

數(shù)據(jù)范圍

1≤n≤50000

輸入樣例：

7

輸出樣例：

3

樣例解釋

一種方案為：4→3→1→7。

可以把每個數(shù)字看成一個點，求得問題轉(zhuǎn)換為求樹的直徑

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 50010;int n;
vector<int> g[N];
int ans;
bool st[N];
int sum[N];int get(int x)
{int res = 1;for(int i = 2; i * i <= x; i ++){if(x % i == 0){res += i;if(x / i != i)res += x / i;}}return res;
}int dfs(int u, int father)
{int d1 = 0, d2 = 0;for(auto j : g[u]){if(j == father)continue;int d = dfs(j, u) + 1;if(d > d1)d2 = d1, d1 = d;else if(d > d2)d2 = d;}ans = max(ans, d1 + d2);return d1;
}int main()
{IOScin >> n;for (int i = 1; i <= n; i ++)for (int j = 2; j <= n / i; j ++)sum[i * j] += i;for (int i = 2; i <= n; i ++)if (sum[i] < i){g[sum[i]].push_back(i);g[i].push_back(sum[i]);}dfs(1, -1);cout << ans;return 0;
}

二叉蘋果樹

有一棵二叉蘋果樹，如果樹枝有分叉，一定是分兩叉，即沒有只有一個兒子的節(jié)點。

這棵樹共?N?個節(jié)點，編號為?1?至?N，樹根編號一定為?1。

我們用一根樹枝兩端連接的節(jié)點編號描述一根樹枝的位置。

一棵蘋果樹的樹枝太多了，需要剪枝。但是一些樹枝上長有蘋果，給定需要保留的樹枝數(shù)量，求最多能留住多少蘋果。

這里的保留是指最終與1號點連通。

輸入格式

第一行包含兩個整數(shù)?N?和?Q，分別表示樹的節(jié)點數(shù)以及要保留的樹枝數(shù)量。

接下來?N?1 行描述樹枝信息，每行三個整數(shù)，前兩個是它連接的節(jié)點的編號，第三個數(shù)是這根樹枝上蘋果數(shù)量。

輸出格式

輸出僅一行，表示最多能留住的蘋果的數(shù)量。

數(shù)據(jù)范圍

1≤Q<N≤100.
N≠1,
每根樹枝上蘋果不超過?30000個。

輸入樣例：

5 2
1 3 1
1 4 10
2 3 20
3 5 20

輸出樣例：

21

有依賴的背包問題的簡化版

f[u][j]表示節(jié)點u，可分配樹枝數(shù)量為j，最大值? ? （j也可理解為背包容量，但也有點不一樣，這個容量不包括本身在內(nèi)）

理解寫在注釋里了

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 110, M = 210;int n, m;
int h[N], e[M], w[M], ne[M], idx;
int f[N][N];void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}void dfs(int u, int father)
{for(int i = h[u]; i != -1; i = ne[i])//第i個物品組{//int j = e[i];if(e[i] == father)continue;dfs(e[i], u);for(int j = m; j >= 0; j --)//背包容量{for(int k = 0; k < j; k ++)//不同決策{f[u][j] = max(f[u][j], f[u][j - k - 1] + f[e[i]][k] + w[i]);//分組背包是物品組里的每個物品體積和價值不同//            f[u][i-1][j]    f[u][i-1][j-vk] + w}}}
}int main()
{IOSmemset(h, -1, sizeof h);cin >> n >> m;for(int i = 1; i < n; i ++){int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b, a, c);}dfs(1, -1);cout << f[1][m];return 0;
}

戰(zhàn)略游戲

鮑勃喜歡玩電腦游戲，特別是戰(zhàn)略游戲，但有時他找不到解決問題的方法，這讓他很傷心。

現(xiàn)在他有以下問題。

他必須保護(hù)一座中世紀(jì)城市，這條城市的道路構(gòu)成了一棵樹。

每個節(jié)點上的士兵可以觀察到所有和這個點相連的邊。

他必須在節(jié)點上放置最少數(shù)量的士兵，以便他們可以觀察到所有的邊。

你能幫助他嗎？

例如，下面的樹：

只需要放置?1?名士兵（在節(jié)點?1?處），就可觀察到所有的邊。

輸入格式

輸入包含多組測試數(shù)據(jù)，每組測試數(shù)據(jù)用以描述一棵樹。

對于每組測試數(shù)據(jù)，第一行包含整數(shù)?N，表示樹的節(jié)點數(shù)目。

接下來?N?行，每行按如下方法描述一個節(jié)點。

節(jié)點編號：(子節(jié)點數(shù)目) 子節(jié)點 子節(jié)點 …

節(jié)點編號從?0?到?N?1，每個節(jié)點的子節(jié)點數(shù)量均不超過?10，每個邊在輸入數(shù)據(jù)中只出現(xiàn)一次。

輸出格式

對于每組測試數(shù)據(jù)，輸出一個占據(jù)一行的結(jié)果，表示最少需要的士兵數(shù)。

數(shù)據(jù)范圍

0<N≤1500,
一個測試點所有?N?相加之和不超過?300650。

輸入樣例：

4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)

輸出樣例：

1
2

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 1510;int n;
vector<int> g[N];
int d[N];
int f[N][2];void dfs(int u)
{f[u][0] = 0;f[u][1] = 1;for(auto j : g[u]){dfs(j);f[u][0] += f[j][1];f[u][1] += min(f[j][0], f[j][1]);}
}int main()
{IOSwhile(cin >> n){for(int i = 0; i <= n; i ++){g[i].clear();d[i] = 0;f[i][0] = f[i][1] = 0;}int ver1, ver2, num;char tmp;for(int i = 0; i < n; i ++){cin >> ver1 >>tmp >> tmp >> num >> tmp;for(int i = 0; i < num; i ++){cin >> ver2;g[ver1].push_back(ver2);d[ver2] ++;}}int root;for(int i = 0; i < n; i ++){if(!d[i]){root = i;break;}}dfs(root);cout << min(f[root][0], f[root][1]) << endl;}return 0;
}

皇宮看守

太平王世子事件后，陸小鳳成了皇上特聘的御前一品侍衛(wèi)。

皇宮各個宮殿的分布，呈一棵樹的形狀，宮殿可視為樹中結(jié)點，兩個宮殿之間如果存在道路直接相連，則該道路視為樹中的一條邊。

已知，在一個宮殿鎮(zhèn)守的守衛(wèi)不僅能夠觀察到本宮殿的狀況，還能觀察到與該宮殿直接存在道路相連的其他宮殿的狀況。

大內(nèi)保衛(wèi)森嚴(yán)，三步一崗，五步一哨，每個宮殿都要有人全天候看守，在不同的宮殿安排看守所需的費用不同。

可是陸小鳳手上的經(jīng)費不足，無論如何也沒法在每個宮殿都安置留守侍衛(wèi)。

幫助陸小鳳布置侍衛(wèi)，在看守全部宮殿的前提下，使得花費的經(jīng)費最少。

輸入格式

輸入中數(shù)據(jù)描述一棵樹，描述如下：

第一行?n，表示樹中結(jié)點的數(shù)目。

第二行至第?n+1 行，每行描述每個宮殿結(jié)點信息，依次為：該宮殿結(jié)點標(biāo)號?i，在該宮殿安置侍衛(wèi)所需的經(jīng)費?k，該結(jié)點的子結(jié)點數(shù)?m，接下來?m?個數(shù)，分別是這個結(jié)點的?m?個子結(jié)點的標(biāo)號?r1,r2,…,rm。

對于一個?n?個結(jié)點的樹，結(jié)點標(biāo)號在?1?到?n?之間，且標(biāo)號不重復(fù)。

輸出格式

輸出一個整數(shù)，表示最少的經(jīng)費。

數(shù)據(jù)范圍

1≤n≤1500

輸入樣例：

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

輸出樣例：

25

樣例解釋：

在2、3、4結(jié)點安排護(hù)衛(wèi)，可以觀察到全部宮殿，所需經(jīng)費最少，為 16 + 5 + 4 = 25。

本來以為和上一題差不多結(jié)果wa了

發(fā)現(xiàn)有一種情況是上一題沒有的：?

選1、4點也是符合要求的

f[u][0] 不放，但能被父節(jié)點看到
f[u][1] 不放，但能被子節(jié)點看到
f[u][2] 放?

f[u][0]和f[u][2]都很好像，主要是如何得到f[u][1]，能被子節(jié)點看到，那就選能被哪個子節(jié)點看到，其他點取min(f[u][1], f[u][2]),在所有方案中選個最小值

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 1510;int n;
vector<int> g[N];
int w[N], d[N];
int f[N][3];
//f[u][0] 不放，但能被父節(jié)點看到
//f[u][1] 不放，但能被子節(jié)點看到
//f[u][2] 放 void dfs(int u)
{f[u][0] = 0, f[u][1] = 0, f[u][2] = w[u];int sum = 0;for(auto j : g[u]){dfs(j);f[u][0] += min(f[j][1], f[j][2]);sum += min(f[j][1], f[j][2]);f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);}int res = 2e9;for(auto j : g[u]){res = min(res, sum + f[j][2] - min(f[j][1], f[j][2]));}f[u][1] = res;
}int main()
{IOScin >> n;for(int i = 0; i < n; i ++){int id, val, num;cin >> id >> val >> num;w[id] = val;for(int j = 0; j < num; j ++){int x;cin >> x;d[x] ++;g[id].push_back(x);}}int root;for(int i = 1; i <= n; i ++){if(!d[i]){root = i;break;}}dfs(root);cout << min(f[root][1], f[root][2]);return 0;
}