UOJ276[清华集训2016]汽水【二分答案】【点分治】【树状数组】

Z时代
2024-01-10
分类：综合

coding

题目分析：

这种乱七八糟的题目一看就是点分治，答案有单调性，所以还可以二分答案。

我们每次二分的时候考虑答案会不会大于等于某个值，注意到系数$k$是无意义的，因为我们可以通过转化使得$k=0$。

合并的过程相当于很多个向量，加起来后看斜率。

注意单个向量也要判定。

由于有了二分的答案$Ans$。判定变得简单多了，推一下。

令$(A,C)$是从一个点到重心的一个向量，$(B,D)$是从另一个点到重心的向量。其中$A$和$B$是重心到该点的路径权值和，$C$和$D$是经过的边数。

$-k \leq \frac{A+C}{B+D} \leq k \Rightarrow -k(B+D) \leq A+C \leq k(B+D)$.

进一步的$A+kB \geq -C-kD$且$A-kB \leq kD-C$。虽然有四元，但是顺序相互关联，所以实际只有两元，排序后树状数组就可以解决啦。

  1 #include<bits/stdc++.h>
  2usingnamespace std;
  3
  4 typedef longlong ll;
  5
  6constint maxn = 50100;
  7
  8 ll k,md; int flag = 0,num,n,rnum;
  9 vector <pair<int,ll> > g[maxn];
 10int arr[maxn],sz[maxn],imp[maxn],cnt[maxn];
 11struct node{ll A;int B,pla;}op[maxn];
 12
 13int cmp(node X,node Y){
 14return -X.A-md*X.B < -Y.A-md*Y.B;
 15}
 16
 17struct Fenwick{
 18int C[maxn];
 19void Add(int now){
 20while(now <= rnum){C[now] ++; now += (now&-now);}
 21    }
 22int query(int now){
 23int ans = 0;
 24while(now){ans += C[now]; now -= (now&-now);}
 25return ans;
 26    }
 27}T1;
 28
 29void read(){
 30     scanf("%d%lld",&n,&k);
 31for(int i=1;i<n;i++){
 32int x,y;longlong v; scanf("%d%d%lld",&x,&y,&v); v -= k;
 33    g[x].push_back(make_pair(y,v)); g[y].push_back(make_pair(x,v));
 34    }
 35}
 36
 37void dfs1(int now,int fa,int dp){
 38     sz[now] = 1;imp[now] = 0;
 39for(auto it : g[now]){
 40if((arr[it.first] && arr[it.first] < dp) || fa == it.first) continue;
 41     dfs1(it.first,now,dp); sz[now] += sz[it.first];
 42    }
 43}
 44
 45int dfs2(int now,int fa,int dp,int ssz){
 46int ans = 0;
 47for(auto it : g[now]){
 48if((arr[it.first] && arr[it.first] < dp) || fa == it.first) continue;
 49int data = dfs2(it.first,now,dp,ssz);
 50if(ans==0 || imp[ans] > imp[data])ans = data;
 51     imp[now] = max(sz[it.first],imp[now]);
 52    }
 53     imp[now] = max(imp[now],ssz-sz[now]);
 54if(ans==0 || imp[ans] > imp[now]) ans = now;
 55return ans;
 56}
 57
 58void dfs3(int now,int fa,int dp,int A,int B){
 59for(auto it : g[now]){
 60if(it.first == fa || (arr[it.first] && arr[it.first] < dp)) continue;
 61     op[++num] = (node){A+it.second,B+1,it.first};
 62     dfs3(it.first,now,dp,A+it.second,B+1);
 63    }
 64}
 65
 66longlong lisan[maxn];
 67void solve(int dr){
 68     rnum = num;
 69for(int i=1;i<=num;i++){lisan[i] = -op[i].A+md*op[i].B;}
 70     sort(lisan+1,lisan+num+1);rnum = unique(lisan+1,lisan+num+1)-lisan-1;
 71for(int i=1;i<=rnum;i++) T1.C[i]=0;
 72for(int i=num,j=1;i>=1;i--){
 73while(j <= num && (-op[j].A-md*op[j].B < op[i].A+md*op[i].B)){
 74         T1.Add(lower_bound(lisan+1,lisan+rnum+1,-op[j].A+md*op[j].B)-lisan);
 75         j++;
 76    }
 77int ans=j-1-T1.query(upper_bound(lisan+1,lisan+rnum+1,op[i].A-md*op[i].B)-lisan-1);
 78if(op[i].A-md*op[i].B < -op[i].A+md*op[i].B && j > i)ans--;
 79if(dr == 1){
 80if(ans - cnt[op[i].pla]){flag = 1;return;}
 81     }else{cnt[op[i].pla] = ans;}
 82    }
 83}
 84
 85void divide(int now,int dp,int lst,longlong AA){
 86     dfs1(now,0,dp); int heavy = dfs2(now,0,dp,sz[now]);arr[heavy] = dp;
 87for(auto it : g[heavy]){
 88if(arr[it.first]&&arr[it.first]<dp) continue;
 89     divide(it.first,dp+1,heavy,it.second);
 90if(flag == 1) return;
 91    }
 92     num = 0; dfs3(heavy,0,dp,0,0); sort(op+1,op+num+1,cmp);
 93     solve(1); num = 0;
 94if(lst) {
 95     num = 0;dfs3(now,0,dp,AA,1);
 96     sort(op+1,op+num+1,cmp);
 97for(int i=1;i<=num;i++) cnt[op[i].pla] = 0;
 98     solve(0);
 99    }
100}
101
102void work(){
103longlong l = 0,r = 1e13;
104while(l < r){
105     md = (l+r)/2; flag = 0;
106     memset(arr,0,sizeof(arr));
107     divide(1,1,0,0);
108if(flag) r = md; else l = md+1;
109    }
110     printf("%lld",l-1);
111}
112
113int main(){
114    read();
115    work();
116return0;117 }