[NOIP2015]运输计划

一句话题意：在一棵n个结点的树上，有m对点对，若将其中一条边的边权修改成0，求m对点对的最大距离的最小值。

这道题正解是二分 树上差分，可是我一开始并没有想到，而是想了另外一个方法。

预处理每对节点的距离（LCA），同时找出最长链，缩短的边一定在这条链上。此过程为O(nlogn)。

枚举链上每一条边，对于所有点对，可以分成两种了：1）经过这条边的点对；2）不经过的。

判断方法：割掉这条边，判断两点是否连通，仍连通，说明不经过，反之经过。于是一棵树就被拆成了两棵。对于经过的路径（包含最长的），距离都会被缩短，但因为最长的路径存在，所以无需考虑经过的其他路径；而不经过的路径之中取个最大值，将最长路径减去边的权和不经过该边的最大值中再取最大值，枚举所有边的时候再取个最小值就OK了。

在链上一条接着一条判断边时，其中的一棵子树会获得更多的节点，其中可能就包括端点，获得其中一个表示此点对经过该边，获得另一个表示不经过了，因为都在子树中连通。这个过程中判断完所有的边后，所有节点都转至子树中，复杂度为O(n)。

对于判断不经过该边的点对的最大值，维护个线段树，开始时维护第i个点对距离d[i]，在得到一个端点后修改成0，另一个也得到时修改回来。此过程为O(nlogn)。

分析结束。

一开始写错了几个细节，15pts；

后来改成了80pts；

再后来改成了95pts；

被一个答案为0的数据卡到了，改正后，100pts。

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <cmath>  5   6 using namespace std;  7   8 #define re register int  9 #define LL long long 10 #define rep(i, x, y) for (register int i = x; i <= y;   i) 11 #define repd(i, x, y) for (register int i = x; i >= y; --i) 12 #define maxx(a, b) a = max(a, b) 13 #define minn(a, b) a = min(a, b) 14  15 inline int read() { 16     int w = 0, f = 1; char c = getchar(); 17     while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar(); 18     while (isdigit(c)) w = (w << 3)   (w << 1)   (c ^ 48), c = getchar(); 19     return w * f; 20 } 21  22 const int maxn = 3e5   5; 23  24 struct Edge { 25     int u, v, w, pre; 26 }; 27  28 struct Gph { 29     int n, m, G[maxn]; 30     Edge edges[maxn << 1]; 31     void init(int n) { 32         this->n = n; 33         m = 0; 34         memset(G, 0, sizeof(G)); 35     } 36     void AddEdge(int u, int v, int w) { 37         edges[  m] = (Edge){u, v, w, G[u]}; 38         G[u] = m; 39     } 40 } ES1, ES2; 41  42 struct LCA { 43     int fa[20][maxn], dis[20][maxn], n, m, dep[maxn]; 44     void dfs(int u, int f) { 45         rep(i, 1, log2(dep[u])) fa[i][u] = fa[i-1][fa[i-1][u]], dis[i][u] = dis[i-1][u]   dis[i-1][fa[i-1][u]]; 46         for (re i = ES1.G[u]; i; i = ES1.edges[i].pre) { 47             Edge &e = ES1.edges[i]; 48             if (e.v == f) continue; 49             fa[0][e.v] = u, dep[e.v] = dep[u]   1, dis[0][e.v] = e.w; 50             dfs(e.v, u); 51         } 52     } 53     int query(int u, int v) { 54         if (dep[u] < dep[v]) u ^= v ^= u ^= v; 55         re res = 0; 56         if (dep[u] != dep[v]) { 57             re dt = dep[u] - dep[v], t = 0; 58             while (dt) { 59                 if (dt & 1) res  = dis[t][u], u = fa[t][u]; 60                 t  ; 61                 dt >>= 1; 62             } 63         } 64         if (u == v) return res; 65         repd(i, log2(dep[u]), 0) 66             if (fa[i][u] != fa[i][v]) res  = dis[i][u]   dis[i][v], u = fa[i][u], v = fa[i][v]; 67         return res   dis[0][u]   dis[0][v]; 68     } 69 } LCA; 70  71 struct SegTree { 72     int val[maxn << 4]; 73     #define lson (o << 1) 74     #define rson (o << 1 | 1) 75     void pushup(int o) { 76         val[o] = max(val[lson], val[rson]); 77     } 78     void build(int o, int l, int r, int *a) { 79         if (l == r) { val[o] = a[l]; return; } 80         re mid = l   r >> 1; 81         build(lson, l, mid, a); 82         build(rson, mid 1, r, a); 83         pushup(o); 84     } 85     void update(int o, int l, int r, int x, int v) { 86         if (l == r) { val[o] = v; return; } 87         re mid = l   r >> 1; 88         if (x <= mid) update(lson, l, mid, x, v); 89         else update(rson, mid 1, r, x, v); 90         pushup(o); 91     } 92     int query() { 93         return val[1]; 94     } 95 } ST; 96  97 int n, m, l[maxn], r[maxn], dis[maxn], vis[maxn], max_i, fa[maxn], d[maxn], ans; 98  99 void dfs1(int u) {100     vis[u] = 1;101     for (re i = ES1.G[u]; i; i = ES1.edges[i].pre) {102         Edge &e = ES1.edges[i];103         if (vis[e.v]) continue;104         fa[e.v] = u; d[e.v] = e.w;105         dfs1(e.v);106     }107 }108 109 int starr[maxn << 1], g[maxn], cnt = 0, val[maxn << 1], time0[maxn];110 111 void AddPoint(int x, int i) {112     starr[  cnt] = g[x];113     val[cnt] = i;114     g[x] = cnt;115 }116 117 void dfs2(int u) {118     vis[u] = 0;119     for (re i = g[u]; i; i = starr[i]) {120         time0[val[i]]  ;121         if (time0[val[i]] == 1) ST.update(1, 1, n, val[i], 0);122         else ST.update(1, 1, n, val[i], dis[val[i]]);123     }124     for (re i = ES1.G[u]; i; i = ES1.edges[i].pre) {125         Edge &e = ES1.edges[i];126         if (!vis[e.v] || e.v == fa[u]) continue;127         dfs2(e.v);128     }129 }130 131 int main() {132     n = read(), m = read();133     ES1.init(n);134     rep(i, 1, n-1) {135         re u = read(), v = read(), w = read();136         ES1.AddEdge(u, v, w);137         ES1.AddEdge(v, u, w);138     }139     LCA.fa[0][1] = 1;140     LCA.dfs(1, -1);141     rep(i, 1, m) {142         l[i] = read(); r[i] = read();143         AddPoint(l[i], i);144         AddPoint(r[i], i);145         dis[i] = LCA.query(l[i], r[i]);146         if (dis[i] > dis[max_i]) max_i = i;147     }148     ST.build(1, 1, n, dis);149     dfs1(l[max_i]);150     ans = dis[max_i];151     while (r[max_i] != l[max_i]) {152         dfs2(r[max_i]);153         minn(ans, max(ST.query(), dis[max_i] - d[r[max_i]]));154         r[max_i] = fa[r[max_i]];155     }156     printf("%d", ans);157     return 0;158 }

 

来源：http://www.icode9.com/content-4-49751.html