P9175 [COCI2022-2023#4] Mreža
可以很容易就想到的一个点是单次询问的答案是有单调性的，大于答案的最低速度的花费肯定是要大于经费或者不存在的，小于答案的都可以按答案的方案修改，因此可以二分。
假设现在二分出来了一个最低速度，可以肯定的是在路径上所有低于这个速度的路都需要升级。
于是很容易发现的是答案的上界就是在路径上升级过后的路的速度的最小值。
这个能直接跳树法乱搞。
想在链上的情况，可以直接用主席树差分获得路径上低于某个速度的路的升级总花费。
在树上的话直接差分就完事了。
时间复杂度
还可以直接在主席树上差分，复杂度能减掉一个
离散化一下应该跑的更快。
考试时 town 了写的树剖，但是三个
树剖兼普通二分代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
//typedef long long llong;
const int MaxN=100000;
int n,q;
struct Edge{
Edge(){}
Edge(int before,int cost,int after)
:before(before),cost(cost),after(after){}
int before,cost,after;
};
Edge edge[MaxN+1];
vector<pair<int,int> >g[MaxN+1];
struct Vertex{
int prt,pEdge,deep;
int size,tagSon,cTop;
int root;
}vert[MaxN+1];
int ani[MaxN+1][18],minRoad[MaxN+1][18];
void PrepareDfs(int u){
vert[u].size=1;
for(auto&pi:g[u]){
int v=pi.first,id=pi.second;
if(v==vert[u].prt)continue;
vert[v].prt=u;
vert[v].pEdge=id;
vert[v].deep=vert[u].deep+1;
PrepareDfs(v);
vert[u].size+=vert[v].size;
if(vert[v].size>vert[vert[u].tagSon].size)vert[u].tagSon=v;
}
}
void Prepare(){
PrepareDfs(1);
for(int i=1;i<=n;i++){
ani[i][0]=vert[i].prt;
minRoad[i][0]=edge[vert[i].pEdge].after;
}
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i<=n;i++){
ani[i][j]=ani[ani[i][j-1]][j-1];
minRoad[i][j]=min(minRoad[i][j-1],minRoad[ani[i][j-1]][j-1]);
}
}
}
int LCA(int a,int b){
if(vert[a].deep<vert[b].deep)swap(a,b);
int k=log2(vert[a].deep-vert[b].deep);
while(k>=0){
if((1<<k)<=vert[a].deep-vert[b].deep)a=ani[a][k];
k--;
}
if(a==b)return a;
k=log2(vert[a].deep);
while(k>=0){
if((1<<k)<=vert[a].deep&&ani[a][k]!=ani[b][k]){
a=ani[a][k];
b=ani[b][k];
}
k--;
}
return vert[a].prt;
}
int GetMinRoad(int a,int b){
if(vert[a].deep<vert[b].deep)swap(a,b);
int k=log2(vert[a].deep-vert[b].deep),ans=INT_MAX;
while(k>=0){
if((1<<k)<=vert[a].deep-vert[b].deep){
ans=min(ans,minRoad[a][k]);
a=ani[a][k];
}
k--;
}
if(a==b)return ans;
k=log2(vert[a].deep);
while(k>=0){
if((1<<k)<=vert[a].deep&&ani[a][k]!=ani[b][k]){
ans=min(ans,minRoad[a][k]);
ans=min(ans,minRoad[b][k]);
a=ani[a][k];
b=ani[b][k];
}
k--;
}
ans=min(ans,minRoad[a][0]);
ans=min(ans,minRoad[b][0]);
return ans;
}
struct Node{
int val;
int l,r;
int lc,rc;
int mid(){return (l+r)/2;}
}tree[MaxN*100+1];
int treeSize=0;
int NewNode(){return ++treeSize;}
int NewNode(int l,int r){
int p=NewNode();
tree[p].l=l,tree[p].r=r;
return p;
}
int Left(int u){return tree[u].lc?tree[u].lc:tree[u].lc=NewNode(tree[u].l,tree[u].mid());}
int Right(int u){return tree[u].rc?tree[u].rc:tree[u].rc=NewNode(tree[u].mid()+1,tree[u].r);}
void PushUp(int u){
tree[u].val=0;
if(tree[u].lc)tree[u].val+=tree[tree[u].lc].val;
if(tree[u].rc)tree[u].val+=tree[tree[u].rc].val;
}
int Add(int u,int pos,int val){
if(pos<tree[u].l||tree[u].r<pos)return u;
int p=NewNode();
tree[p]=tree[u];
if(tree[u].l==tree[u].r){
tree[p].val+=val;
return p;
}
if(pos<=tree[u].mid())
tree[p].lc=Add(Left(u),pos,val);
else
tree[p].rc=Add(Right(u),pos,val);
PushUp(p);
return p;
}
int Ask(int u,int l,int r){
if(r<tree[u].l||tree[u].r<l)return 0;
if(l<=tree[u].l&&tree[u].r<=r)return tree[u].val;
int sum=0;
if(tree[u].lc)sum+=Ask(tree[u].lc,l,r);
if(tree[u].rc)sum+=Ask(tree[u].rc,l,r);
return sum;
}
void ChainDfs(int u,int cTop){
vert[u].cTop=cTop;
if(cTop==u){
vert[u].root=NewNode(1,1e9);
vert[u].root=Add(
vert[u].root,
edge[vert[u].pEdge].before,
edge[vert[u].pEdge].cost
);
}else{
vert[u].root=Add(
vert[vert[u].prt].root,
edge[vert[u].pEdge].before,
edge[vert[u].pEdge].cost
);
}
for(auto&pi:g[u]){
int v=pi.first;
if(v==vert[u].prt)continue;
if(vert[u].tagSon!=v)
ChainDfs(v,v);
else
ChainDfs(v,cTop);
}
}
void Solve(){
cin>>n;
for(int i=1;i<=n-1;i++){
int u,v,a,b,c;
cin>>u>>v>>a>>b>>c;
g[u].emplace_back(v,i);
g[v].emplace_back(u,i);
edge[i]=Edge(a,b,c);
}
Prepare();
ChainDfs(1,1);
cin>>q;
for(int i=1;i<=q;i++){
int a,b,e;
cin>>a>>b>>e;
vector<int>rootSet;
pair<int,int>spec;
int lca=LCA(a,b);
int u=a;
while(vert[u].cTop!=vert[lca].cTop){
rootSet.emplace_back(vert[u].root);
u=vert[vert[u].cTop].prt;
}
int v=b;
while(vert[v].cTop!=vert[lca].cTop){
rootSet.emplace_back(vert[v].root);
v=vert[vert[v].cTop].prt;
}
if(u!=v){
if(vert[u].deep<vert[v].deep)
spec=make_pair(vert[u].root,vert[v].root);
else
spec=make_pair(vert[v].root,vert[u].root);
}
int l=0,r=GetMinRoad(a,b)-1,mid;
while(l<r){
mid=(l+r+1)/2;
int sum=0;
for(int root:rootSet)sum+=Ask(root,1,mid);
sum+=Ask(spec.second,1,mid)-Ask(spec.first,1,mid);
if(sum<=e)
l=mid;
else
r=mid-1;
}
cout<<l+1<<'\n';
}
}
#undef int
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
Solve();
return 0;
}Update 2023/12/11
被海客了
二分值域设错了
充分说明了这道题的数据之水