Codeforces 1060E(dfs计数)

题意

给一棵树，对于一个节点，与它相邻的结点可以连一条边，求所有点对间距离之和

思路

任意两点间的距离 $s$ 被优化为$\left \lceil \frac{s}{2} \right \rceil$，转化为任意两点间距加间距为奇数的路径数，即$\frac{\sum_{i\in G,j\in G,i<j}dis[i][j]+\sum_{i\in G,j\in G,i<j[dis[i][j]=1(mod 2)]}}{2}$，奇数路径可由深度奇偶性不同的点数相乘得到，即$\sum_{i\in G}dep[i]=1(mod 2)*\sum_{i\in G}dep[i]=0(mod2)$

代码

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <map>

#include <set>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <cassert>

#include <cstring>

#include <iostream>

#include <algorithm>

#define IOS    ios::sync_with_stdio(0),cin.tie(0);

#define DBG(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long LL;

typedef long double LD;

typedef unsigned long long ULL;

const int inf = 0x3f3f3f3f;

const int mod = 1000000007;

const double eps = 1e-8;

const double pi  = acos(-1.0);

void file(){

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

}

const int maxn = 2e5+5;

const int maxm = 4e5+5;

int n;

int head[maxn],tot;

int dep[maxn],vis[maxn];

LL cnt0,cnt1;

LL siz[maxn];

struct edgenode{

    int to,next;

}edge[maxm];

void addedge(int u,int v){

    edge[tot].to=v;

    edge[tot].next=head[u];

    head[u]=tot++;

}

void dfs(int x,int dep){

    siz[x]=1;

    if(vis[x] == inf){

        vis[x]=dep;

        if(abs(dep)%2 == 0)cnt0++;

        else cnt1++;

    }

    for(int i=head[x];i != -1;i=edge[i].next){

        int v=edge[i].to;

        if(vis[v] == inf){

            dfs(v,dep+1);

            siz[x]+=siz[v];

        }

    }

}

namespace BakuretsuMahou{

    void Explosion(){

        memset(head,-1,sizeof head);

        memset(vis,0x3f,sizeof vis);

        scanf("%d",&n);

        for(int i=1;i<n;i++){

            int a,b;

            scanf("%d%d",&a,&b);

            addedge(a,b);

            addedge(b,a);

        }

        dfs(1,0);

        LL ans=cnt0*cnt1;

        for(int i=1;i<=n;i++)

            ans+=siz[i]*(1LL*n-siz[i]);

        printf("%I64d\n",ans/2);

    }

}

int main(){

    //IOS

    //file();

    BakuretsuMahou::Explosion();

    return 0;

}

巴特西

Codeforces 1060E(dfs计数)

最新文章

热门文章