比赛 |
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);
}
}
}