「火」烈火燎原

NC53678. 「火」烈火燎原

描述

帕秋莉掌握了一种火属性魔法

这种强大的魔法可以让一棵树瞬间化为灰烬！

现在有一棵树G（无环），定义它的“小树”是X(G)，小树X(G)的点集是G的边集

在“小树”中，两点之间有边，当且仅当这两个点对应的边在原图上有公共点

完整版的魔法可以将一棵树的小树的小树的小树的小树的小树的小树……全部烧掉

但帕秋莉不想消耗那么多的魔法来干这种无聊的事，毕竟她只想用这个魔法来修建树枝罢了

于是她想问你，对于一棵她想修剪的树G，它的X(X(G))有多少个点？

输入描述

第一行一个正整数n表示G的点数；
接下来n-1 行，每行两个数表示G的一条边

输出描述

输出一行，一个整数表示答案

示例1

输入:

输出:

说明:

下图是想修剪的树G

图二是G的小树X(G)

图三是X(X(G))

由图知，它有四个点

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 44ms, 内存消耗: 872K, 提交时间: 2019-11-23 20:25:51

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int n,d[110000],x,y;
long long ans;
int main(){
	scanf("%d",&n);
	fo(i,2,n){
		scanf("%d%d",&x,&y);
		d[x]++;
		d[y]++;
	}
	fo(i,1,n) ans+=d[i]*1ll*(d[i]-1)/2;
	printf("%lld\n",ans);
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 60ms, 内存消耗: 804K, 提交时间: 2023-05-03 22:21:03

#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main(){
    int n,s=0,x,y,i;
    cin>>n;
    while(--n){
        cin>>x>>y;
        a[x]++,a[y]++;
    }
    for(i=1;i<=100000;i++)s+=a[i]*(a[i]-1)/2;
    cout<<s;
}