---

題目描述：

Another attempt of revising toll system is rejected by the people of Byteland. The Government is inbig trouble now. They are seeking help of Hashmat, the brave warrior and the great programmer ofByteland to solve the problem. Hashmat has come up with a new idea to fix this toll managementproblem.There are N cities and M bidirectional highways among these cities. The government proposedsome toll (may be different toll for different highways) for each of the highways. But people think theyare being over charged. Hashmat’s idea was to make both the people and the Government happy. Inhis plan he decided to keep the toll of the highways as it is in Government’s proposal but he wouldpublish a special set of N ? 1 highways. There are two conditions for a set of N ? 1 highways to bespecial. These N ? 1 highways have to connect all the cities and a person will be able to go from acity to any other city spending minimum toll in any of these highways. Please note, using these specialhighways does not guarantee minimum sum of toll but it guarantees you minimum individual toll.People of Byteland are happy with the idea of special highway, but the Government is not happyas they want more toll from the highway sector. They called up a meeting and formed a committee tofind two values for all the highways. Let these values be Ai and Bi for the i-th highway and defined asfollows:1) Ai

The maximum amount of toll they can add to the i-th highway so that Hashmat’s set remains
special.
2) Bi

The maximum amount of toll they can decrease from the i-th highway so that Hashmat’s set
remains special.
In other words, if Ci
is the current toll of the i-th highway, then if the Government updates the toll
of the highway to Ci + Ai (or Ci ? Bi), Hashmat’s set remains special. Please note, while finding out
Ai and Bi other tolls remain unchanged.
This time Hashmat does not want to help the Government. He thinks this is a conspiracy against
the people of Byteland. So they came to you. Will you help them to find out Ai and Bi for all the
highways?
Input
First line of the input contains a positive integer T (T < 25), denoting the number of test cases.
First line of each test contains two integer numbers N and M (1 ≤ N ≤ 10000, N ? 1 ≤ M ≤
100000), denoting the number of city and number of highway respectively. Each of the next M lines
contains the description of a highway, where the i-th line contains three integer numbers Ui
, Vi and Ci
(1 ≤ U i, V i ≤ N, U i ?= V i, 0 ≤ Ci ≤ 1000), that means there is a highway between city Ui and city
Vi and the toll of the highway is Ci
. You may consider the highways to be bidirectional. Note that
the first N ? 1 highways in the input are the special highways. You may assume that there will be no
invalid data in the input file.
Output
For each test case, output the test case number and a single integer S, where
S =
∑
M
i=1
(i ? Ai + i
2
? Bi)

題解：

其實是一道很裸的題目. 唯一需要想的是,對于樹邊,它增大的時候需要考慮所有跨過它的非樹邊,那么反著想,就是所有非樹邊更新它這條鏈上的所有樹邊.之后就是邊的樹鏈剖分.

重點：

1.樹邊獲取和用非樹邊更新的關系
2.邊的樹鏈剖分

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <vector>using namespace std;typedef long long ll; const int maxn = 10000 + 100; const int MAXNODE = 4 * maxn + 100; const int M = 10000;struct edge {int to, w;edge(int _to = 0, int _w = 0) {to = _to;w = _w;} }; vector<edge> G[maxn]; int n, deep[maxn], m; int tp[maxn], fa[maxn], son[maxn], w[maxn], no[maxn], fanno[maxn], cnt; int tree[MAXNODE], tag[MAXNODE]; int A[maxn * 10], B[maxn * 10]; int tu[maxn * 10], tv[maxn * 10], tw[maxn * 10]; int st[21][maxn], L2[maxn];void st_initail() {for(int s = 1; s <= 20; s++) {for(int i = 1;i + (1 << s) - 1 <= cnt; i++) {int j = i + (1 << (s - 1));st[s][i] = max(st[s - 1][i], st[s - 1][j]);}} } int st_query(int l, int r) {int len = (r - l + 1);int s = L2[len];return max(st[s][l], st[s][r - (1 << s) + 1]); }void dfs1(int u, int pa) {w[u] = 1;son[u] = 0;for(int i = 0; i < G[u].size(); i++) {int v = G[u][i].to;if(v != pa) {deep[v] = deep[u] + 1;fa[v] = u;dfs1(v, u);w[u] += w[v];if(w[v] > w[son[u]])son[u] = v;}} } void dfs2(int u, int top) {tp[u] = top;cnt++;no[u] = cnt;fanno[cnt] = u;if(son[u] != 0) {dfs2(son[u], top);}for(int i = 0; i < G[u].size(); i++) {int v = G[u][i].to;if(v != fa[u] && v != son[u]) {dfs2(v, v);}} }void dfs3(int u) {for(int i = 0; i < G[u].size(); i++) {int v = G[u][i].to, w = G[u][i].w;if(v != fa[u]) {st[0][no[v]] = w;dfs3(v);}}}void initail(int rt, int l, int r) {//printf("aaa %d %d %d\n", rt, l, r);tree[rt] = M;tag[rt] = M;if(l == r) {;}else {int mid = (l + r) / 2;initail(rt * 2, l, mid);initail(rt * 2 + 1, mid +1, r);} }void pushDown(int rt) {if(tag[rt] == M)return;int lrt = 2 * rt, rrt = 2 * rt + 1;tag[lrt] = min(tag[lrt], tag[rt]);tag[rrt] = min(tag[rrt], tag[rt]);tree[lrt] = min(tree[lrt], tag[rt]);tree[rrt] = min(tree[rrt], tag[rt]);tag[rt] = M; } void pushUp(int rt) {int lrt = 2 * rt, rrt = 2 * rt + 1;tree[rt] = min(tree[lrt], tree[rrt]); }void update(int L, int R, int k, int rt, int l, int r) {//printf("ccc %d %d %d\n", rt, l, r);if(L <= l && R >= r) {tag[rt] = min(tag[rt], k);tree[rt] = min(tree[rt], k);return;}pushDown(rt);int mid = (l + r) / 2, lrt = 2 * rt, rrt = lrt + 1;if(L <= mid) {update(L, R, k, lrt, l, mid);}if(R >= mid + 1) {update(L, R, k, rrt, mid + 1, r);}pushUp(rt); } int query(int pos, int rt, int l, int r) {if(l == r) {return tree[rt];}pushDown(rt);int mid = (l + r) / 2, lrt = 2 * rt, rrt = 2 * rt + 1;if(pos <= mid)return query(pos, lrt, l, mid);return query(pos, rrt, mid + 1, r); }void change(int u, int v, int k) {int tpu = tp[u], tpv = tp[v];while(tpu != tpv) {if(deep[tpu] < deep[tpv]) {swap(tpu, tpv);swap(u, v);}update(no[tpu], no[u], k, 1, 1, cnt);u = fa[tpu];tpu = tp[u];}if(u == v)return;if(deep[u] < deep[v]) {swap(u, v);}//printf("bbb %d %d %d\n", no[son[v]], no[u], k);update(no[son[v]], no[u], k, 1, 1, cnt); }int queryMax(int u, int v) {int ans = 0;int tpu = tp[u], tpv = tp[v];while(tpu != tpv) {if(deep[tpu] < deep[tpv]) {swap(tpu, tpv);swap(u, v);}ans = max(ans, st_query(no[tpu], no[u]));u = fa[tpu];tpu = tp[u];}if(u == v)return ans;if(deep[u] < deep[v])swap(u, v);// printf("888 %d %d\n", u, v);ans = max(ans, st_query(no[son[v]], no[u]));return ans;}void solve() {memset(st[0], 0, sizeof(st[0]));memset(deep, 0, sizeof(deep));memset(w, 0, sizeof(w));dfs1(1, 0);//printf("%d %d %d\n", getLCA(2, 3), getLCA(2, 3), getLCA(1, 3));tp[1] = 1;cnt = 0;dfs2(1, 1);initail(1, 1, cnt);//printf("%d\n", cnt);dfs3(1);st_initail();//printf("777 %d %d\n", queryMax(1, 3), no[2]);for(int i = 0; i < m - (n - 1); i++) {int u, v, c;scanf("%d %d %d", &u, &v, &c);A[n - 1 + i] = -1;B[n - 1 + i] = c - queryMax(u, v);//printf("666 %d\n", B[n - 1 + i]);change(u, v, c);}for(int i = 0; i < n - 1; i++) {B[i] = -1;int t = tu[i];if(deep[tu[i]] > deep[tv[i]])t = tu[i];elset = tv[i];A[i] = query(no[t], 1, 1, cnt);if(A[i] == M) {A[i] = -1;}else {A[i] = A[i] - tw[i];}}ll ans = 0;for(int i = 0; i < m; i++) {//printf("ddd %d %d %d\n", i, A[i], B[i]);ans = ans + (ll)(i + 1) * (ll)A[i] + (ll)(i + 1) * (ll)(i + 1) * (ll)B[i];}printf("%lld\n", ans); }int main() {//freopen("c.txt", "r", stdin);L2[0] = -1;for(int i = 1; i <= 10000; i++) {if((i & (i - 1)) == 0)L2[i] = L2[i - 1] + 1;elseL2[i] = L2[i - 1];}int ncase;scanf("%d", &ncase);for(int _ = 1; _ <= ncase; _++) {printf("Case %d: ", _);scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++)G[i].clear();for(int i = 0; i < n - 1; i++) {int u, v, c;scanf("%d%d%d", &u, &v, &c);G[u].push_back(edge(v, c));G[v].push_back(edge(u, c));tu[i] = u;tv[i] = v;tw[i] = c;}solve();}return 0; }

總結

以上是生活随笔為你收集整理的UVALive 7338 C - Toll Management IV的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。