玄学求助
  • 板块灌水区
  • 楼主Zkl21
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/9/3 18:29
  • 上次更新2023/11/2 22:50:52
查看原帖
玄学求助
661164
Zkl21楼主2023/9/3 18:29

想问一下我这道题代码注释的部分为啥不对?好像没有什么变量重名的问题,不知道到底哪里出问题了,有没有大佬知道原因?

#include<iostream>
#include<cstring>
using namespace std;
const int N=3e5+10,M=N<<1;
int n,m,u[N],v[N],d[N],p[N],lca[N],l,r;
int h[N],e[M],ne[M],w[M],idx,edge[N];
void add(int a,int b,int c)
{
    e[++idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx;
}
int dep[N],fa[N],top[N],rw[N],s[N],son[N],dist[N],cnt;
void dfs(int u,int father,int depth)
{
    s[u]=1,dep[u]=depth,fa[u]=father,rw[++cnt]=u;
    for(int i=h[u];i;i=ne[i])
    {
        int j=e[i];
        if(j==fa[u])continue;
        edge[j]=w[i];
        dist[j]=dist[u]+w[i];
        dfs(j,u,depth+1);
        s[u]+=s[j];
        if(s[son[u]]<s[j])son[u]=j;
    }
}
void dfs(int u,int t)
{
    top[u]=t;
    if(!son[u])return;
    dfs(son[u],t);
    for(int i=h[u];i;i=ne[i])
    {
        int j=e[i];
        if(j==fa[u]||j==son[u])continue;
        dfs(j,j);
    }
}
int LCA(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    return x;
}
bool check(int x)
{
    int sum=0;
    memset(p,0,sizeof p);
    for(int i=1;i<=m;i++)
        if(d[i]>x)
        {
            p[u[i]]++,p[v[i]]++,p[lca[i]]-=2;
            sum++;
        }
    for(int i=n;i;i--)
    {
        p[fa[rw[i]]]+=p[rw[i]];
        if(edge[rw[i]]>=r-x&&p[rw[i]]==sum)return 1;
    }
    return 0;
}
int main()
{
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
        l=max(l,c);
    }
    dfs(1,0,1);
    dfs(1,1);
    for(int i=1;i<=m;i++)
    {
        cin>>u[i]>>v[i];
        lca[i]=LCA(u[i],v[i]);
        d[i]=dist[u[i]]+dist[v[i]]-2*dist[lca[i]];
        r=max(r,d[i]);
    }
    // l=r-l,r++;
    // while(l<r)
    // {
    //     int mid=l+r>>1;
    //     if(check(mid))r=mid;
    //     else l=mid+1;
    // }
    // cout<<l<<"\n";
    int ll=r-l,rr=r+1;
    while(ll<rr)
    {
        int mid=ll+rr>>1;
        if(check(mid))rr=mid;
        else ll=mid+1;
    }
    cout<<ll<<"\n";
    return 0;
}
2023/9/3 18:29
加载中...