题解 | #变异蛮牛#

属实没想到E题是这样的难度... 一个dfs遍历黑点数解决

using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int N = 2e5+8;
int t,n,vis[N],u,v;
ll num;
vector<int>e[N];
void dfs(int cur,int step){
    if(vis[cur])return ;
    if(step&1)num++;
    vis[cur]=1;
    for(int i=0;i<e[cur].size();i++){
        int now = e[cur][i];
        dfs(now,step+1);
    }
}
int main()
{
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<=n;i++)e[i].clear();
        num=0;
        for(int i=1;i<=n-1;i++){
            cin>>u>>v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        dfs(1,1);
        cout<<num+num*(num-1)/2;
    }
}