codeforces 110E Lucky Tree

传送门：https://codeforces.com/contest/110/problem/E

题意：给你一颗树，节点与节点之间的边有一个边权，定义只由4和7组成的数字是幸运数字，现在要你求一共有多少条路径，使得节点u->v之间至少存在一条边为幸运数字

题解：树形dp+容斥，我们要找有多少条路径上至少存在一条幸运边，那么我们就可以找到所有的不含幸运路径的边然后用所有路径和减去不含幸运路径的边即可

　　　1，每次输入边权的时候处理边权是否为幸运数字，如果是，那么为1，否则为0

　　　2，dfs处理，如果边权为0，那么不含幸运数字的路径+1；

　　　3，容斥，因为是一个三元组，我们先从n个点选一个点，再从n-1个点选一个点，再从n-2个点选一个点，那么一共有n*（n-1）*（n-2）种选取三元组的方法。

　　　　如果这个第i个节点存在没有幸运边的情况，那么就从这些边中选3条，方法数是tmp*(tmp-1)*(tmp-2)，这是i->j,i->k都没有幸运数的情况

　　　　另外一种是i->j没有幸运数但i->k有幸运数，或者i->j有幸运数，但i->k没有幸运数的情况为2*tmp*(tmp-1)*(n-tmp)

代码如下:

#include <map>

#include <set>

#include <cmath>

#include <ctime>

#include <stack>

#include <queue>

#include <cstdio>

#include <cctype>

#include <bitset>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <functional>

#define fuck(x) cout<<"["<<x<<"]";

#define FIN freopen("input.txt","r",stdin);

#define FOUT freopen("output.txt","w+",stdout);

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

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;

const int maxn = 1e5+;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9+;

struct node{

    int v,next;

    LL w;

}edge[maxn<<];

int head[maxn],tot;

LL dp[maxn];

void add(int u,int v,int w){

    edge[tot].v=v;

    edge[tot].w=w;

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

    head[u]=tot++;

}

void dfs(int u,int fa){

    dp[u]=;

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

        int v=edge[i].v;

        if(v==fa) continue;

        dfs(v,u);

        if(edge[i].w==){

            dp[u]+=dp[v]+;

            dp[v]=;

        }

    }

}

int main(){

#ifndef ONLINE_JUDGE

    FIN

#endif

    int u,v;

    LL n,w,f;

    tot=;

    memset(head,-,sizeof(head));

    scanf("%lld",&n);

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

        scanf("%d%d%lld",&u,&v,&w);

        f=;

        while(w){

            if(w%!=&&w%!=) f=;

            w/=;

        }

        add(u,v,f);

        add(v,u,f);

    }

    if(n<=){

        printf("0\n");

        return ;

    }

    dfs(,);

    LL ans=(LL)n*(n-)*(n-);

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

        if(dp[i]){

            LL tmp=dp[i]+;

            ans-=tmp*(tmp-)*(tmp-);

            ans-=tmp*(tmp-)*((LL)n-tmp)*;

        }

    }

    cout<<ans<<endl;

}

巴特西

codeforces 110E Lucky Tree

最新文章

热门文章