[数据结构与算法]51Nod - 1588 幸运树（DFS）

题目链接：51nod1588幸运树

思路

可以发现先看一个点，找出这个点走非幸运的边最多能走到s个点（最少为1），这个点的贡献答案就是(n-s)*(n-s-1)，也就是从(n-s)个点中选择两个点，还要*2

接下来就是统计每个点走非幸运边，能走到多少个其他点

也就是找连通块，而且一个s点的连通块，这s个点的答案都是s个，用dfs的搜索即可，走过的点就不用走，没有过的找出该点最大的连通块

这题似乎还是有树形DP做法的，不过应该是比较麻烦。

代码

#include<bits/stdc++.h>
using namespace std;
#define fo(a,b) for(int i=a;i<=b;i++)
#define inf 0x3f3f3f3f
#define ll long long
#define M 1000010
int n;
ll dp[M],vis[M],s=0,sum=0;
struct Node
{
    vector<pair<int,int>>v;
}x[M];
int f(int a){        //判断幸运边
    while(a){
        if(a%10!=7&&a%10!=4) return 0;
        a/=10;
    }
    return 1;
}
void dfs(int d,vector<pair<int,int>>&v,int pre)
{
    s++;
    vis[d]=1;
    int l=v.size();
    for(int i=0;i<l;i++){
        int now=v[i].first;
        int data=v[i].second;
        if(now!=pre&&(!vis[now])&&data==0){        //走没走过且不幸运的边
            dfs(now,x[now].v,d);
        }
    }
}
int main()
{
    cin>>n;
    for(int a,b,c,i=1;i<n;i++){
        scanf("%d%d%d",&a,&b,&c);
        x[a].v.push_back(make_pair(b,f(c)));
        x[b].v.push_back(make_pair(a,f(c)));
    }
    fo(1,n){        //1-n点搜索，搜索过的不再搜索
        s=0;
        if(!vis[i]){
            dfs(i,x[i].v,0);
        }
        sum+=s*(n-s)*(n-s-1);        //s个点的答案一样，相乘即可
    }
    cout<<sum<<endl;
	return 0;
}