社区讨论

数组开小了竟然会MLE

P3398仓鼠找 sugar参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi6tevvr
此快照首次捕获于
2025/11/20 10:31
4 个月前
此快照最后确认于
2025/11/20 10:31
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxx=100005;
struct data
{
    int to,nt;
}node[maxx];
int xx,yy,zz,dd;
int son[maxx],father[maxx],dep[maxx],sz[maxx],top[maxx],head[maxx];
int tot,n,m;
void add_node(int x,int y)
{
    node[++tot].to=y;
    node[tot].nt=head[x];
    head[x]=tot;
}
void dfs1(int x,int fa)
{	
    father[x]=fa;
    dep[x]=dep[fa]+1;
    sz[x]=1;
    for(int i=head[x];i;i=node[i].nt)
    {
        int j=node[i].to;
        if(j!=fa)
        {
            dfs1(j,x);
            sz[x]+=sz[j];
            if(sz[j]>sz[son[x]])son[x]=j;
        }
    }
}
void dfs2(int x,int tp)
{
    top[x]=tp;
    if(!son[x])return;
    dfs2(son[x],tp);
    for(int i=head[x];i;i=node[i].nt)
    {
        int j=node[i].to;
        if(j!=father[x]&&j!=son[x])dfs2(j,j);
    }
}
int lca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        x=father[top[x]];
    }
    if(dep[x]<dep[y])return x;
    return y;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&xx,&yy);
        add_node(xx,yy);add_node(yy,xx);
    }
    dfs1(1,1);
    dfs2(1,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&xx,&yy,&zz,&dd);
        if(xx==zz||yy==dd||xx==dd||yy==zz){printf("Y\n");continue;}
        int temp=max(dep[lca(xx,yy)],dep[lca(zz,dd)]);
        int rr=max(max(dep[lca(xx,zz)],dep[lca(xx,dd)]),max(dep[lca(yy,zz)],dep[lca(yy,dd)]));
        if(rr>=temp)printf("Y\n");
        else printf("N\n");
    }
    return 0;
}


回复

2 条回复,欢迎继续交流。

正在加载回复...