牛客練習試合40 C題
16217 ワード
タイトルリンク:https://ac.nowcoder.com/acm/contest/369/Cタイトルの説明
Aさんはあなたに木をあげました.この木の縁ごとに、任意の(0でもよい)回(すなわち、このエッジが接続されている2つの点の間に1つのエッジ権が同じエッジを追加する)をコピーして、新しく形成される可能性のあるすべての図の中でオーラ路の最短長さを求めることができます.オーラ路:図のいずれかの点から図のいずれかの点が終わる経路を求め、図の各エッジはちょうど1回しか通過しません.
説明の第1行の1つの数nを入力して、ノードの個数の次のn-1行を表して、各行の3つの整数u,v,w、uからvの辺権がwの無方向の辺の保証データが1本の木であることを表します
出力記述1行1整数、答えを表す
入力サンプル41 2 11 3 11 4 2
出力サンプル5
1つの可能なスキームは、<1,2,1>のエッジを1回複製することであり、オーラルは4−>1−>2−>1−>3である.
データ範囲1≦n≦2×1051≤ui,vi≤n1≤wi≤104
構想:まず定義を理解します:オラ回路:図の中の任意の点から始まり、終了時にその点の経路に戻り、図の中の各エッジはちょうど1回しか通過しません.つまり、オラロードの起点と終点が一つです.このとき、ツリー全体を巡って戻りたい場合は、所有権値の和の2倍になります.オラロードは起点と終点に要求されず、起点から終点までの経路は1回しか計算されない.答えは、所有権値の2倍-数のうち2点の距離が最も長い値です.テーマは数を求める直径,すなわち樹上の重み距離が最も長い2点に変換される.
第1の解法:両側dfsはs-tが最も長い経路であると仮定し、まず任意の点nからこの点から最も遠い点mを探し、その点mはsとtの中の点に違いない.m点からこの点から最も遠い点qを探すと,m−qはs−tである.
第2の解法:ツリーdp
iをルートノードとするサブツリーでは、通過点iの最大直径は、iからリーフノードまでの最大距離と二次大距離の和である.dp[i]は、iをルートノードとしてリーフノードまでの最大距離、dp[i]=max(dp[i],dp[iのサブノードj]+i~jまでの距離)として定義される.一方、更新のたびに直径ans=max(ans,dp[i]+dp[j]+iからjまでの距離)を求めることができ、このときdp[i]はノードjを含まない最も遠い距離であるため、現在のdp[i]+dp[j]+iからjまでの距離が最大距離と二次大距離である.
賞
キャンディをごちそうしてくれてありがとう
Aさんはあなたに木をあげました.この木の縁ごとに、任意の(0でもよい)回(すなわち、このエッジが接続されている2つの点の間に1つのエッジ権が同じエッジを追加する)をコピーして、新しく形成される可能性のあるすべての図の中でオーラ路の最短長さを求めることができます.オーラ路:図のいずれかの点から図のいずれかの点が終わる経路を求め、図の各エッジはちょうど1回しか通過しません.
説明の第1行の1つの数nを入力して、ノードの個数の次のn-1行を表して、各行の3つの整数u,v,w、uからvの辺権がwの無方向の辺の保証データが1本の木であることを表します
出力記述1行1整数、答えを表す
入力サンプル41 2 11 3 11 4 2
出力サンプル5
1つの可能なスキームは、<1,2,1>のエッジを1回複製することであり、オーラルは4−>1−>2−>1−>3である.
データ範囲1≦n≦2×1051≤ui,vi≤n1≤wi≤104
構想:まず定義を理解します:オラ回路:図の中の任意の点から始まり、終了時にその点の経路に戻り、図の中の各エッジはちょうど1回しか通過しません.つまり、オラロードの起点と終点が一つです.このとき、ツリー全体を巡って戻りたい場合は、所有権値の和の2倍になります.オラロードは起点と終点に要求されず、起点から終点までの経路は1回しか計算されない.答えは、所有権値の2倍-数のうち2点の距離が最も長い値です.テーマは数を求める直径,すなわち樹上の重み距離が最も長い2点に変換される.
第1の解法:両側dfsはs-tが最も長い経路であると仮定し、まず任意の点nからこの点から最も遠い点mを探し、その点mはsとtの中の点に違いない.m点からこの点から最も遠い点qを探すと,m−qはs−tである.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
using namespace std;
typedef long long ll;
template <class T>
inline void read(T &n) {
T ans = 0;
char ch = '+';
int flag = 0;
while (ch<'0' || ch>'9') {
ch = getchar();
if (ch == '-')
flag = 1;
}
while (ch >= '0'&&ch <= '9') {
ans = ans * 10 + ch - 48;
ch = getchar();
}
n = flag == 1 ? -ans : ans;
}
vectorint , ll> >a[200100];
ll dis[200100];
int node;
ll ans;
void dfs(int x, int fa) {
for (int i = 0; i < a[x].size(); i++) {
if (a[x][i].first != fa) {
dis[a[x][i].first] = dis[x] + a[x][i].second;
if (ans < dis[a[x][i].first]) {
ans = dis[a[x][i].first];
node = a[x][i].first;
}
dfs(a[x][i].first, x);
}
}
}
int main() {
int n;
read(n);
int x, y;
ll z, sum = 0;
for (register int i = 1; i < n; i++) {
read(x), read(y), read(z);
a[x].push_back(pair<int, ll>(y, z));
a[y].push_back(pair<int, ll>(x, z));
sum += z * 2;
}
//cout << sum << endl;
ans = 0;
dis[1] = 0;
dfs(1, 0);
//cout << node << endl;
ans = 0;
dis[node] = 0;
dfs(node, 0);
printf("%lld
", sum - ans);
//system("pause");
}
第2の解法:ツリーdp
iをルートノードとするサブツリーでは、通過点iの最大直径は、iからリーフノードまでの最大距離と二次大距離の和である.dp[i]は、iをルートノードとしてリーフノードまでの最大距離、dp[i]=max(dp[i],dp[iのサブノードj]+i~jまでの距離)として定義される.一方、更新のたびに直径ans=max(ans,dp[i]+dp[j]+iからjまでの距離)を求めることができ、このときdp[i]はノードjを含まない最も遠い距離であるため、現在のdp[i]+dp[j]+iからjまでの距離が最大距離と二次大距離である.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const long long mod = 1e8 + 7;
ll dp[maxn];
struct node {
int s, e, w, next;
}a[maxn * 2];
int head[maxn];
ll len, ans;
void add(int s, int e, int w) {
a[len].e = e;
a[len].w = w;
a[len].next = head[s];
head[s] = len++;
}
void dfs(int x, int fa) {
for (int i = head[x]; i != -1; i = a[i].next) {
int y = a[i].e;
if (y == fa)
continue;
dfs(y,x);
ans = max(ans, dp[x] + dp[y] + a[i].w);
dp[x] = max(dp[x], dp[y] + a[i].w);
}
}
int main() {
int n;
scanf("%d", &n);
memset(head, -1, sizeof(head));
len = 0, ans = 0;
int x, y, z;
ll sum = 0;
for (int i = 1; i < n; i++) {
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
add(y, x, z);
sum += z * 2;
}
dfs(1, -1);
printf("%lld
", sum - ans);
}
賞
キャンディをごちそうしてくれてありがとう