P2680 运输计划（二分+树上差分）

P2680 运输计划

链接

分析：

　　二分+树上差分。

　　首先可以二分一个答案，那么所有比这个答案大的路径，都需要减去些东西才可以满足这个答案。

　　那么减去的这条边一定在所有的路径的交集上。

　　那么如果求快速的求出这个交集并判断呢，树剖可以，把所有大于的路径都标记一下，然后判断，复杂度太大了。

　　于是用到了树上差分，get新技能。

　　在两个端点出标记+1，在lca出标记-2，然后从叶子节点往上更新，对于一条边是交集，那么它标记的次数一定是大于这个答案的个数。然后判断是否满足即可。

　　各种优化：1、L,R的范围，2、可以按dis排序，发现没什么用。

代码

  1 // luogu-judger-enable-o2
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<iostream>
  7 #include<cctype>
  8 
  9 using namespace std;
 10 
 11 const int N = 300100;
 12 struct Edge{
 13     int nxt,to,w;
 14     Edge() {}
 15     Edge(int a,int b,int c) {to = a,w = b,nxt = c;}
 16 }e[600100];
 17 struct Que{
 18     int u,v,lca,dis;
 19     bool operator < (const Que &A) const {
 20         return dis > A.dis;
 21     }
 22 }q[N];
 23 int head[N],tot;
 24 int deth[N],fa[N],num[N],dis[N],val[N],f[N][23],tag[N];
 25 int n,m,dfs_time;
 26 
 27 inline char nc() {
 28     static char buf[100000],*p1 = buf,*p2 = buf;
 29     return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
 30 }
 31 inline int read() {
 32     int x = 0,f = 1;char ch = nc();
 33     for (; !isdigit(ch); ch=nc()) if(ch=='-') f=-1;
 34     for (; isdigit(ch); ch=nc()) x=x*10+ch-'0';
 35     return x * f;
 36 }
 37 void add_edge(int u,int v,int w) {
 38     e[++tot] = Edge(v,w,head[u]);head[u] = tot;
 39     e[++tot] = Edge(u,w,head[v]);head[v] = tot;
 40 }
 41 void dfs(int u,int fa) {
 42     num[++dfs_time] = u;
 43     deth[u] = deth[fa] + 1;
 44     f[u][0] = fa;
 45     for (int i=head[u]; i; i=e[i].nxt) {
 46         int v = e[i].to;
 47         if (v == fa) continue;
 48         dis[v] = dis[u] + e[i].w;
 49         val[v] = e[i].w;
 50         dfs(v,u);
 51     }
 52 }
 53 void init() {
 54     for (int j=1; j<=22; ++j) 
 55         for (int i=1; i<=n; ++i) 
 56             f[i][j] = f[f[i][j-1]][j-1];
 57 }
 58 int Lca(int u,int v) {
 59     if (deth[u] < deth[v]) swap(u,v);
 60     int d = deth[u] - deth[v];
 61     for (int i=22; i>=0; --i) 
 62         if (d & (1 << i)) u = f[u][i];
 63     if ( u == v ) return u;
 64     for (int i=22; i>=0; --i) 
 65         if (f[u][i] != f[v][i]) 
 66             u = f[u][i],v = f[v][i];
 67     return f[u][0];
 68 }
 69 bool check(int x) {
 70     memset(tag,0,sizeof(tag));
 71     int limit = 0,cnt = 0;
 72     for (int i=1; i<=m; ++i) {
 73         if (q[i].dis > x) { // 找到所有大于x的 
 74             tag[q[i].u] ++; tag[q[i].v] ++; tag[q[i].lca] -= 2; // 差分 
 75             limit = max(limit,q[i].dis - x); // 最少减去多少 
 76             cnt ++;
 77         }
 78     }
 79     if (!cnt) return true; //如果没有大于x的，直接返回true，加上这句快了不少。 
 80     for (int i=n; i>=1; --i) 
 81         tag[f[num[i]][0]] += tag[num[i]];
 82     for (int i=2; i<=n; ++i) 
 83         if (val[i] >= limit && tag[i] == cnt) return true;
 84     return false;
 85 }
 86 int main () {
 87     n = read(),m = read();
 88     int L = 0,R = 0;
 89     for (int i=1; i<n; ++i) {
 90         int u = read(),v = read(),w = read();
 91         add_edge(u,v,w);
 92         L = max(L,w);
 93     }
 94     dfs(1,0);
 95     init();
 96     for (int i=1; i<=m; ++i) {
 97         q[i].u = read(),q[i].v = read();
 98         q[i].lca = Lca(q[i].u,q[i].v);
 99         q[i].dis = dis[q[i].u] + dis[q[i].v] - dis[q[i].lca] * 2;
100         R = max(R, q[i].dis);
101     }
102 //    sort(q+1,q+m+1);
103     int ans = R;
104     while ( L <= R )    { 
105         int mid = ( L + R ) / 2;
106         if (check(mid)) ans = mid,R = mid - 1;
107         else L = mid + 1;
108     }
109     cout << ans;
110     return 0;
111 }