QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#697449 | #8333. Gift | KOH-# | WA | 1ms | 5740kb | C++14 | 2.1kb | 2024-11-01 14:08:29 | 2024-11-01 14:08:29 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)) f|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;return;
}
template <typename T>
inline void print(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10^48);return;
}
#define ll long long
const int N=1e5+3;
int head[N],to[N<<1],Next[N<<1],tot;
void Addedge(int u,int v){
to[++tot]=v,Next[tot]=head[u],head[u]=tot;
return;
}
int in[N],id[N],n;
bool Cmp(int x,int y){
return in[x]>in[y];
}
int fa[N],dep[N],cnt;
bool ring[N];
void Dfs(int u,int f){
dep[u]=dep[f]+1,fa[u]=f;
// cout<<u<<" "<<dep[u]<<"???\n";
for(int i=head[u];i;i=Next[i]){
int v=to[i];
// cout<<u<<" "<<v<<"??\n";
if(v==f) continue;
if(dep[v]<dep[u]&&dep[v]){
int now=u;ring[u]=true;
while(now!=v&&now){
now=fa[now];
ring[now]=true;
// cout<<now<<"???\n";
}
cnt=dep[v]-dep[u]+1;
}
else Dfs(v,u);
}
}
int main(){
// int T;read(T);
// while(T--){
read(n);
for(int i=1;i<=n;++i){
id[i]=i;int u,v;read(u),read(v);
Addedge(u,v),Addedge(v,u);
in[u]++,in[v]++;
}
id[n]=n;
sort(id+1,id+n+1,Cmp);
Dfs(1,0);
if(in[id[1]]>5){
puts("0");
}
else if(in[id[n]]==0){
puts("0");
}
else{
if(in[id[3]]==5) puts("0");
else if(in[id[1]]!=5){
print(1ll*(n-1)*cnt),putchar('\n');
}
else{
if(in[id[2]]==5){
if(ring[id[1]]&&ring[id[2]]) print(n-1),putchar('\n');
else puts("0");
}
else{
if(ring[id[1]]){
int res=0;
for(int i=head[id[1]];i;i=Next[i]){
// int y=to[i];cout<<y<<"??\n"
if(ring[to[i]]) res++;
}
print(1ll*(n-1)*res),putchar('\n');
}
else puts("0");
}
}
}
// for(int i=1;i<=n;++i) id[i]=head[i]=fa[i]=dep[i]=in[i]=0,ring[i]=false;
// for(int i=1;i<=tot;++i) to[i]=Next[i]=0;
// tot=0;
// }
return 0;
}
/*
5
1 2
2 4
4 3
1 3
1 4
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3652kb
input:
6 1 2 1 3 1 4 1 5 1 6 2 3
output:
10
result:
ok 1 number(s): "10"
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 5740kb
input:
3 1 3 3 2 2 1
output:
-2
result:
wrong answer 1st numbers differ - expected: '9', found: '-2'