NC207654. HappyFairy
描述
There are N cities in the world that are connected by N- 1 roads. All the cities are connected like a tree (a tree is an acyclic undirected connected graph). The cities are marked as 1, 2, ...,N. The natural environment on each road is different. We use wi to indicate the temperature on the i-th road (-109 ≤ wi ≤ 109, 1 ≤ i ≤N - 1, 1 ≤ N ≤ 100,000).
Mia is a happy fairy who loves to travel. She will depart from her city X to city Y(1 ≤ X, Y ≤ N). Mia's body temperature is C(-109 ≤ C ≤ 109). She has prepared a dress with thickness P and K portals (P ≥ 0, 0 ≤ K ≤ 109). For the i-th road (1 ≤ i ≤ N - 1), Mia can only pass the road if and only if the temperature of the road wi is no less than C - P (otherwise she will freeze to death) and no more than C + P (otherwise she will be burned). In the meantime, Mia can use one portal to transfer between two cities connected by one road, no matter how cold or hot the road is. One portal can be used only once to pass one road. Mia wants to bring a dress as thin as possible (i.e. a dress with thickness P as small as possible) so that she can survive her journey from city X to city Y. Please help her find a suitable dress.
输入描述
The first line is an integer T (1 ≤ T ≤ 5), indicates that there are T-group data.
For each test case, the first line contains two integers N, Q. N is the number of cities. Q is the number of queries (1 ≤ N, Q ≤ 100,000).
The following N - 1 lines describe the roads, the i-th of which contains three integers ui, vi, wi, indicating there is a road between city ui and city vi with temperature wi (1 ≤ ui, vi ≤ N, ui≠vi, -109 ≤ wi ≤ 109, 1 ≤ i ≤ N - 1).
The following Q lines describe the queries, each of which contains four integers X, Y, C, K, meaning the journey starts from X and ends in Y, while Mia's body temperature during this journey is C, carrying K portals (1 ≤ X, Y ≤ N, -109 ≤ C ≤ 109, 0 ≤ K ≤ 109).
输出描述
For each test case, output Q lines, each of which is the minimum thickness P (P ≥ 0) of Mia's dress during her journey.
示例1
输入:
2 5 2 1 3 3 1 2 3 3 4 2 3 5 2 2 4 3 0 2 4 2 0 9 5 1 2 20 1 3 27 2 4 36 2 5 44 5 8 72 5 9 69 3 6 33 3 7 78 5 7 50 2 5 8 72 0 5 8 30 1 5 8 30 2 8 8 50 0
输出:
1 1 23 0 0 0 0
C++14(g++5.4) 解法, 执行用时: 4950ms, 内存消耗: 41804K, 提交时间: 2020-06-07 17:33:25
#include<bits/stdc++.h>
#define dd(x) cout<<#x<<" = "<<x<<" "
#define de(x) cout<<#x<<" = "<<x<<"\n"
#define sz(x) int(x.size())
#define All(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef priority_queue<int> BQ;
const double eps=1e-8;
inline int sign(double x){return (x>eps)-(x<-eps);}
const int maxn=1e5+100,mod=1e9+7,INF=0x3f3f3f3f;
vector<ll> d;
inline int hs(ll x){
return lower_bound(All(d),x)-d.begin()+1;
}
int id,cnt[maxn*22],ls[maxn*22],rs[maxn*22],rt[maxn];
void upd(int pre,int& now,int c,int l,int r){
now=++id;
cnt[now]=cnt[pre]+1;
ls[now]=ls[pre];
rs[now]=rs[pre];
if (l==r) return;
int m=l+r>>1;
if (c<=m) upd(ls[pre],ls[now],c,l,m);
else upd(rs[pre],rs[now],c,m+1,r);
}
int qry(int pre,int now,int c,int l,int r){
if (l==r){
return cnt[now]-cnt[pre];
}
int m=l+r>>1;
if (c>m)
return cnt[ls[now]]-cnt[ls[pre]]+qry(rs[pre],rs[now],c,m+1,r);
else
return qry(ls[pre],ls[now],c,l,m);
}
vector<P> e[maxn];
int fa[maxn][25],dep[maxn];
void dfs(int u,int ff){
fa[u][0]=ff;
dep[u]=dep[ff]+1;
for (int i=1;i<=22;++i)
fa[u][i]=fa[fa[u][i-1]][i-1];
for (auto v:e[u])
if (v.fi!=ff){
upd(rt[u],rt[v.fi],hs(v.se),0,sz(d)+1);
dfs(v.fi,u);
}
}
inline int Lca(int x,int y){
if (dep[x]<dep[y])
swap(x,y);
for (int i=22,d=dep[x]-dep[y];i>=0;--i)
if ((d>>i)&1)
x=fa[x][i];
if (x==y) return x;
for (int i=22;i>=0;--i)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
inline bool check(int x,int y,int c,int k,ll p){
int lca=Lca(x,y);
int l=hs(c-p)-1,r=hs(c+p+1)-1;
int sum=0;
sum+=qry(rt[lca],rt[x],l,0,sz(d)+1)+dep[x]-dep[lca]-qry(rt[lca],rt[x],r,0,sz(d)+1);
// de(qry(rt[lca],rt[x],l,0,sz(d)+1));
// de(dep[x]-dep[lca]);
// de(qry(rt[lca],rt[x],r,0,sz(d)+1));
sum+=qry(rt[lca],rt[y],l,0,sz(d)+1)+dep[y]-dep[lca]-qry(rt[lca],rt[y],r,0,sz(d)+1);
// de(qry(rt[lca],rt[y],l,0,sz(d)+1));
// de(dep[y]-dep[lca]);
// de(qry(rt[lca],rt[y],r,0,sz(d)+1));
// dd(c),dd(p),dd(l),de(r);
// dd(x),dd(y),de(lca);
return sum<=k;
}
void init(int n){
for (int i=1;i<=n;++i){
e[i].clear();
}
d.clear();
id=0;
}
int main()
{
int T;
cin>>T;
while (T--){
int n,q;
scanf("%d%d",&n,&q);
init(n);
for (int i=1;i<n;++i){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[u].pb(mp(v,w));e[v].pb(mp(u,w));
d.pb(w);
}
sort(All(d));
d.erase(unique(All(d)),d.end());
dfs(1,0);
for (int qq=1;qq<=q;++qq){
int x,y,c,k;
scanf("%d%d%d%d",&x,&y,&c,&k);
if (x==y){
printf("0\n");
continue;
}
ll l=0,r=2e9+3,ans;
while (l<=r){
ll mid=l+r>>1;
if (check(x,y,c,k,mid))
ans=mid,r=mid-1;
else
l=mid+1;
}
printf("%lld\n",ans);
}
}
return 0;
}
/*
1
5 2
1 3 3
1 2 3
3 4 2
3 5 2
2 4 3 0
2 4 2 0
*/
C++ 解法, 执行用时: 1932ms, 内存消耗: 38596K, 提交时间: 2021-07-26 18:47:02
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define INF 0x3f3f3f3f
const int N = 1e5+7;
struct tree{int ls,rs,sum;} t[N<<5];
int n,q,cnt,tot,p[N<<1];
struct {int u,v,w;} edge[N];
int e[N<<1],ne[N<<1],h[N],idx,w[N<<1];
int lg[N<<1]={-1},fa[N][25],dep[N],root[N];
void insert(int &rt,int pre,int l,int r,int x)
{
t[rt=++cnt]=t[pre];
if(l==r){t[rt].sum++;return;}
int mid=l+r>>1;
if(x<=mid)insert(t[rt].ls,t[pre].ls,l,mid,x);
else insert(t[rt].rs,t[pre].rs,mid+1,r,x);
t[rt].sum=t[t[rt].ls].sum+t[t[rt].rs].sum;
}
int query(int u,int v,int lc,int l,int r,ll L,ll R)
{
if(p[l]>=L&&p[r]<=R)return t[u].sum+t[v].sum-t[lc].sum*2;
if(l==r)return 0;
int mid=l+r>>1,ans=0;
if(L<=p[mid])ans+=query(t[u].ls,t[v].ls,t[lc].ls,l,mid,L,R);
if(R>p[mid])ans+=query(t[u].rs,t[v].rs,t[lc].rs,mid+1,r,L,R);
return ans;
}
void add(int u,int v,int val)
{
e[++idx]=v,ne[idx]=h[u],h[u]=idx,w[idx]=val;
}
void dfs(int u,int fath,int val)
{
fa[u][0]=fath,dep[u]=dep[fath]+1;
for(int i=1;i<=lg[dep[u]];i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
insert(root[u],root[fath],1,tot,val);
for(int i=h[u];i;i=ne[i])
if(e[i]!=fath)
dfs(e[i],u,w[i]);
}
int lca(int a,int b)
{
if(dep[a]<dep[b])swap(a,b);
while(dep[a]>dep[b])
a=fa[a][lg[dep[a]-dep[b]]];
if(a==b)return a;
for(int i=lg[dep[a]];i>=0;i--)
if(fa[a][i]!=fa[b][i])
a=fa[a][i],b=fa[b][i];
return fa[a][0];
}
void prework()
{
cnt=idx=0;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)h[i]=root[i]=0;
for(int i=1;i<n;i++)
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w),p[i]=edge[i].w;
sort(p+1,p+n);
tot=unique(p+1,p+n)-p-1;
for(int i=1;i<n;i++)
{
int pp=lower_bound(p+1,p+1+tot,edge[i].w)-p;
add(edge[i].u,edge[i].v,pp);
add(edge[i].v,edge[i].u,pp);
}
dfs(1,0,0);
}
void solve()
{
prework();
while(q--)
{
int u,v,c,k;
scanf("%d%d%d%d",&u,&v,&c,&k);
if(u==v){puts("0");continue;}
int lc=lca(u,v);
int sum=t[root[u]].sum+t[root[v]].sum-t[root[lc]].sum*2;
if(sum<=k){puts("0");continue;}
ll l=0,r=2e9,mid;
while(l<r)
{
mid=l+r>>1;
int tmp=query(root[u],root[v],root[lc],1,tot,c-mid,c+mid);
if(tmp<sum-k)l=mid+1;
else r=mid;
}
printf("%d\n",l);
}
}
int main()
{
for(int i=1;i<=1e5;i++)lg[i]=lg[i>>1]+1;
int T;
cin>>T;
while(T--)solve();
return 0;
}