快手第四题 好序列

直接统计不好序列  路径全为红即为不好序列
每个点记录子节点里有几个点通过不好路径相连
考虑每棵子树对答案的贡献即可
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
struct node
{
    int to;
    int c;
    node(int _to,int _c):to(_to),c(_c){}
};
struct node2
{
    int to;
    int c;
    int num;
     node2(int _to,int _c,int _num):to(_to),c(_c),num(_num){}
};
vector<node>g[100010];
vector<node2>G[100010];
bool vis[100010];
void build(int root){
    if(vis[root]==1) return;
    vis[root]=1;
    for(int i=0;i<g[root].size();i++){
        if(vis[g[root][i].to]==0){
            G[root].push_back(node2(g[root][i].to,g[root][i].c,0));
            build(g[root][i].to);
        }
    }
}
int num[100010],ans=0;
int fast(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b%2==1) ans=1LL*ans*a%mod;
        b/=2;
        a=1LL*a*a%mod;
    }
    return ans;
}
int n,k,l,r,c;
void solve(int root)
{
    num[root]=1;
    for(int i=0;i<G[root].size();i++){
        solve(G[root][i].to);
        if(G[root][i].c==0) {
                num[root]+=num[G[root][i].to];
                ans=(ans+mod-fast(num[G[root][i].to],k))%mod;
        }
    }
    ans=(ans+fast(num[root],k))%mod;
}
int main()
{
    memset(vis,0,sizeof(vis));
    memset(num,0,sizeof(num));
    cin>>n>>k;
    for(int i=0;i<n-1;i++){
        scanf("%d %d %d",&l,&r,&c);
        g[l].push_back(node(r,c));
        g[r].push_back(node(l,c));
    }
    build(1);
    solve(1);
    cout<<(fast(n,k)+mod-ans)%mod<<endl;
}


#快手##笔试题目##题解#
全部评论
点赞 回复 分享
发布于 2019-08-25 20:27
tql
点赞 回复 分享
发布于 2019-08-25 18:36
求教通过了吗,我也统计不好的,用的并查集加快速幂,百分之零
点赞 回复 分享
发布于 2019-08-25 18:34
我想知道这道题到底啥意思。。。
点赞 回复 分享
发布于 2019-08-25 18:33
点赞 回复 分享
发布于 2019-08-25 18:32
大佬!
点赞 回复 分享
发布于 2019-08-25 18:31
大佬。
点赞 回复 分享
发布于 2019-08-25 18:30

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
07-01 17:14
中北大学 Java
兄弟们是真是假
牛客46374834...:我在boss上投java岗从来没成功过
点赞 评论 收藏
分享
06-12 16:23
已编辑
小米_软件开发(准入职员工)
点赞 评论 收藏
分享
评论
2
15
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务