关于CE
  • 板块灌水区
  • 楼主清风雪月
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/3/6 18:26
  • 上次更新2023/10/28 07:07:30
查看原帖
关于CE
388857
清风雪月楼主2022/3/6 18:26

求助各位万能的谷民,这个代码为什么会CE,怎么样修改

#include<bits/stdc++.h>
using namespace std;
typedef long long s64;
template<class T>
inline void read(T &x)
{
    static char ch;
    static bool opt;
    while(!isdigit(ch=getchar())&&ch!='-');
    x=(opt=ch=='-')?0:ch-'0';
    while(isdigit(ch=getchar()))x=x*10+ch-'0';
    if(opt)x=~x+1;
}
inline void tense(int &x,const int &y)
{
    if(x>y)x=y;
}
const int MaxNV=2e4+5;
const int MaxNE=MaxNV<<1;
const int MaxNode=MaxNV<<2;
int n,m,ect,ans[MaxNV],adj[MaxNV],to[MaxNV],nxt[MaxNE],dep[MaxNV],fa[MaxNV],sze[MaxNV],son[MaxNV],seg[MaxNV],rev[MaxNV],top[MaxNV],totpos,sum[MaxNode],tag[MaxNode];
#define trav(u)for(int e=adj[u],v;v=to[e],e;e=nxt[e])
inline void addEdge(const int &u,const int &v)
{
    nxt[++ect]=adj[u],adj[u]=ect,to[ect]=v;
    nxt[++ect]=adj[v],adj[v]=ect,to[ect]=u;
}
inline void init()
{
    ect=0;
    memset(sum,0,sizeof(sum));
    memset(tag,0,sizeof(tag));
    memset(top,0,sizeof(top));
    memset(son,0,sizeof(son));
    memset(adj,0,sizeof(adj));
}
inline void dfs1(const int &u)
{
    dep[u]=dep[fa[u]+1];
    sze[u]=1;
    trav(u)
    {
        if(v!=fa[u])
        {
            fa[v]=u;
            dfs1(v);
            sze[u]+=sze[v];
            if(sze[v]>sze[son[u]])son[u]=v;
        }
    }
}
inline void dfs2(const int &u)
{
    if(son[u])
    {
        rev[seg[son[u]]=++totpos]=son[u];
        top[son[u]]=top[u];
        dfs2(son[u]);
    }
    trav(u)
    {
        if(v!=fa[u]&&v!=son[u])
        {
            rev[seg[v]=++totpos]=v;
            top[v]=v;
            dfs2(v);
        }
    }
}
#define lc(x<<1)
#define rc(x<<1|1)
inline void upt(const int &x)
{
    sum[x]=sum[lc]+sum[rc];
}
inline void add(const int &x,const int &l,const int &r,const int &v)
{
    sum[x]+=v*(r-l+1);
    tag[x]+=v;
}
inline void dnt(const int &x,const int &l,const int &r)
{
    if(tag[x])
    {
        int mid=l+r>>1;
        add(lc,l,mid,tag[x]);
        add(rc,mid+1,t,tag[x]);
        tag[x]=0;
    }
}
inline void my(const int &x,const int &l,const int &r,const int &u,const int &v)
{
    if(u<=l&&r<=v)return add(x,l,r,1);
    dnt(x,l,r);
    int mid=l+r>>1;
    if(u<=mid)my(lc,l,mid,u,v);
    if(v>mid)my(rc,mid+1,r,u,v);
    upt(x); 
}
inline int qq(const int &x,const int &l,const int &t,const int &p)
{
    if(l==r)return sum[x];
    dnt(x,l,r);
    int mid=l+r>>1;
    if(p<=mid)return qq(lc,l,mid,p);
    else return qq(rc,mid+1,r,p); 
}
inline void pm(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])std::swap(u,v);
        my(1,1,n,seg[top[u]],seg[u]);
        u=fa[top[u]];
    }
    if(dep[u]>=dep[v])std::swap(u,v);
    if(u!=v)my(1,1,n,seg[u]+1,seg[v]);
}
int main()
{
    int T;
    read(T);
    while(T--)
    {
        read(n);read(m);
        init();
        for(int i=1,u,v;i<n;i++)
        {
            read(u),read(v);
            addEdge(u,v);
        }
        dfs1(1);
        seg[1]=rev[1]=top[1]=totpos=1;
        dfs2(1);
        int tmp=m-n+1;
        for(int i=1,u,v;i<=tmp;i++)
        {
            read(u),read(v);
            pm(u,v); 
        }
        int ans=m+1;
        for(int i=2;i<=n;i++)tense(ans,qq(1,1,n,seg[i]));
        printf("%d\n",ans+1);
    } 
    return 0;
}
2022/3/6 18:26
加载中...