QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#735543#8333. Giftqikala7777#WA 2ms5776kbC++232.0kb2024-11-11 20:36:142024-11-11 20:36:15

Judging History

你现在查看的是最新测评结果

  • [2024-11-11 20:36:15]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5776kb
  • [2024-11-11 20:36:14]
  • 提交

answer

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef tuple<int,LL,LL> TPL;
typedef pair<LL,LL> PII;
const int N=1e6+7,inf=0x3f3f3f3f;const LL Linf=0x3f3f3f3f3f3f3f3fLL;
LL qsm(LL a,LL b,LL p){LL res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
LL lowbit(LL x){return x&-x;}
int n;
vector<int>g[N];
int du[N];
bool st[N];
void solve(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++)du[i]=g[i].size();
    queue<int>q;
    for(int i=1;i<=n;i++){
        if(du[i]==1)q.push(i);
    }
    while(q.size()){
        int u=q.front();q.pop();
        for(auto v:g[u]){
            du[v]--;
            if(du[v]==1)q.push(v);
        }
    }
    int hcnt=0;
    for(int i=1;i<=n;i++){
        if(du[i]>1){
            st[i]=1;
            hcnt++;
        }
    }
    int cnt=0;
    set<int>aa;
    for(int i=1;i<=n;i++){
        if(g[i].size()==4){
            cnt++;
        }else if(g[i].size()==5){
            aa.insert(i);
        }
    }
    LL sum=0;
    for(int i=1;i<=n;i++){
        if(g[i].size()>3)continue;
        for(auto v:g[i]){
            if(g[v].size()==5){
                if(st[i]){
                    sum++;
                }else{
                    sum+=2;
                }
            }else if(g[v].size()==4){
                if(aa.size())continue;
                if(st[i]&&st[v]){
                    sum+=hcnt-2;
                }else{
                    sum+=hcnt-1;
                }
            }else{
                if(aa.size())continue;
                if(st[i]&&st[v]){
                    sum+=hcnt-2;
                }else{
                    sum+=hcnt-1;
                }
            }
        }
    }
    cout<<sum<<endl;
}
int main(){
   IOS
   int T=1;
   //cin>>T;
    while(T--)solve();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5776kb

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: 2ms
memory: 5632kb

input:

3
1 3
3 2
2 1

output:

-4

result:

wrong answer 1st numbers differ - expected: '9', found: '-4'