比赛 2024暑期C班集训4 评测结果 AAAWWEEEEE
题目名称 飘雪圣域 最终得分 30
用户昵称 wdsjl 运行时间 1.009 s
代码语言 C++ 内存使用 6.06 MiB
提交时间 2024-07-04 10:39:26
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;

const int N = 200;
const int M = 2010;

int uu[M],vv[M],used[M];
int g[N][N],n,q,mapp[N][N],u[N],v[N],vis[N],cnt;

void floyd(int l,int r){
    for(int i=l;i<=r;i++){
        for(int j=l;j<=r;j++){
            for(int k=l;k<=r;k++){
                if(g[j][k]>g[j][i]+g[i][k])g[j][k]=g[j][i]+g[i][k];
            }
        }
    }
}

int main(){
    freopen("icekingdom.in","r",stdin);
    freopen("icekingdom.out","w",stdout);
    scanf("%d%d",&n,&q);
    if(n<=100&&q<=100){
        for(int i=1;i<n;i++){
            scanf("%d%d",&u[i],&v[i]);
        }
        while(q--){
        cnt=0;
        memset(vis,0,sizeof(vis));
        memset(g,0x3f,sizeof(g));
        for(int i=1;i<=n;i++)g[i][i]=0;
        for(int i=1;i<n;i++){
            g[u[i]][v[i]]=1;
            g[v[i]][u[i]]=1;
        }
        int l,r;
        scanf("%d%d",&l,&r);
        for(int i=1;i<=n;i++){
            if(i<l||i>r){
                for(int j=1;j<=n;j++){
                    g[i][j]=0x3f3f3f3f;
                    g[j][i]=0x3f3f3f3f;
                }
            }
        }
        floyd(l,r);
        for(int i=l;i<=r;i++){
            if(vis[i]==0){
                cnt++;
                vis[i]++;
                for(int j=l;j<=r;j++){
                    if(g[i][j]<0x3f3f3f3f)vis[j]++;
                }
            }
        }
        /*for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cout<<g[i][j]<<" ";
            }
            cout<<endl;
        }*/
        printf("%d\n",cnt);
    }
    return 0;
    }else{
        for(int i=1;i<n;i++){
            scanf("%d%d",&uu[i],&vv[i]);
        }
        while(q--){
            cnt=0;
            memset(used,0,sizeof(used));
            int l,r;
            scanf("%d%d",&l,&r);
            for(int i=1;i<n;i++){
                if(uu[i]>=l&&uu[i]<=r&&used[uu[i]]==0){
                    if(vv[i]<l||vv[i]>r){
                        used[uu[i]]++;
                        cnt++;
                    }
                }
                if(vv[i]>=l&&vv[i]<=r&&used[vv[i]]==0){
                    if(uu[i]<l||uu[i]>r){
                        used[vv[i]]++;
                        cnt++;
                    }
                }
            }
            printf("%d\n",cnt);
        }
    }
}