题解：P9175 [COCI2022-2023#4] Mreža

· · 题解

暴力出奇迹！

其实这道题想到整体二分之后就非常好想且好写。我带调试大括号不换行的代码只有二百多行。

对于每个询问，我们二分可能达成的最低车速。注意到性质：

每个社区最多与两个其他社区相连。

这就意味着树是一条链且联想到是路径问题，果断树剖启动。

那么问题就来到了检查 m 组询问，每组询问表示一个路径以及我需要达到的最低车速。

我们把车速离散化然后扔进 vector 里，然后维护一个指针递增表示当前车速。那么我们就可以用树状数组维护当前某段区间的升级代价以及是不是升级了也无法完成，然后这道题就做完了。

喜提最劣解，但是能过。复杂度 O(n \log^3 n)。

代码：

#include<bits/stdc++.h>
#define int long long
#define inf (int)4e18
#define endl '\n'
using namespace std;
void debug(int x){cout << "debug " << x << endl;}
void debug(string s){cout << "debug " << s << endl;}
int n,m;
struct Edge{
    int v,v1,v2,s;
};
vector<Edge>e[100010];
int dep[100010],siz[100010],fa[100010],son[100010];
int v1[100010],v2[100010],s[100010];
void dfs1(int x,int f)
{
    dep[x]=dep[f]+1;
    fa[x]=f;
    for ( int i = 0 ; i < e[x].size() ; i++ )
    {
        int v=e[x][i].v;
        if(v==fa[x])
        {
            continue;
        }
        v1[v]=e[x][i].v1;
        v2[v]=e[x][i].v2;
        s[v]=e[x][i].s;
        dfs1(v,x);
        siz[x]+=siz[v];
        if(siz[son[x]]<siz[v])
        {
            son[x]=v;
        }
    }
    siz[x]++;
}
int top[100010],id[100010],bef[100010],tot;
void dfs2(int x,int head)
{
    if(!x)
    {
        return;
    }
    id[x]=++tot;
    bef[tot]=x;
    top[x]=head;
    dfs2(son[x],head);
    for ( int i = 0 ; i < e[x].size() ; i++ )
    {
        int v=e[x][i].v;
        if(v==son[x]||v==fa[x])
        {
            continue;
        }
        dfs2(v,v);
    }
}
struct Q{
    int u,v,val,l,r,mid,id;
}q[100010];
int check()
{
    for ( int i = 1 ; i <= m ; i++ )
    {
        if(q[i].l!=q[i].r)
        {
            return 0;
        }
    }
    return 1;
}
int cmp(Q p,Q q)
{
    return p.mid<q.mid;
}
vector<int>vec1[200010],vec2[200010];//vec1存当最低车速为x的时候需要升级的道路，vec2存当最低车速为x的时候无法通行的道路 
int t1[100010],t2[100010];
int lowbit(int x){return x&(-x);}
void upd(int t[],int x,int p)
{
    while(x<=n)
    {
        t[x]+=p;
        x+=lowbit(x);
    }
}
int calc(int t[],int x)
{
    int ans=0;
    while(x)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
int getans(int u,int v)
{
    int ans=0;
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])
        {
            swap(u,v);
        }
        int l=id[top[u]],r=id[u];
        if(calc(t2,r)-calc(t2,l-1))
        {
            return inf;
        }
        ans+=calc(t1,r)-calc(t1,l-1);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])
    {
        swap(u,v);
    }
    int l=id[v]+1,r=id[u];
    if(calc(t2,r)-calc(t2,l-1))
    {    
        return inf;
    }    
    ans+=calc(t1,r)-calc(t1,l-1);
    return ans;
}
int ans[100010];
int b[200010],sumb;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n ;
    for ( int i = 1 ; i < n ; i++ )
    {
        int u,v,v1,v2,s;
        cin >> u >> v >> v1 >> s >>v2;
        e[u].push_back({v,v1,v2,s});
        e[v].push_back({u,v1,v2,s});
        b[i*2-1]=v1;
        b[i*2]=v2;
    }
    cin >> m;
//  for ( int i = 1 ; i <= n*2-2 ; i++ )
//  {
//      cout << b[i] << " ";
//  }
//  cout << endl;
    sort(b+1,b+1+n*2-2);
//  debug(1);
    sumb=unique(b+1,b+1+n*2-2)-b-1;
//  debug("lsh");
    dfs1(1,1);
//  debug("114");
    dfs2(1,1);
    for ( int i = 1 ; i <= m ; i++ )
    {
        cin >> q[i].u >> q[i].v >> q[i].val;
        q[i].id=i;
        q[i].l=1;
        q[i].r=sumb;
        q[i].mid=(1+sumb+1)/2;
    }
    for ( int i = 2 ; i <= n ; i++ )
    {
        vec1[lower_bound(b+1,b+1+sumb,v1[i])-b+1].push_back(i);
        vec2[lower_bound(b+1,b+1+sumb,v2[i])-b+1].push_back(i); 
    }
    while(!check())
    {
        sort(q+1,q+1+m,cmp);
        int tot=1;
        memset(t1,0,sizeof(t1));
        memset(t2,0,sizeof(t2));
        for ( int i = 1 ; i <= m ; i++ )
        {
//          debug(q[i].id);
            while(tot<=q[i].mid)
            {
                for ( int j = 0 ; j < vec1[tot].size() ; j++ )
                {
                    int v=vec1[tot][j];
                    upd(t1,id[v],s[v]);
                }
                for ( int j = 0 ; j < vec2[tot].size() ; j++ )
                {
                    int v=vec2[tot][j];
                    upd(t2,id[v],1);
                }
                tot++;
            }
            int x=getans(q[i].u,q[i].v);
//          debug(x);
            if(x<=q[i].val)
            {
                q[i].l=q[i].mid;
            }else{
                q[i].r=q[i].mid-1;
            }
        }
        for ( int i = 1 ; i <= m ; i++ )
        {
            q[i].mid=(q[i].l+q[i].r+1)/2;
        }
    }
    for ( int i = 1 ; i <= m ; i++ )
    {
        ans[q[i].id]=q[i].l;
    }
    for ( int i = 1 ; i <= m ; i++ )
    {
        cout << b[ans[i]]<< endl;
    }
    return 0;
}