牛客练习赛30——小K的疑惑

读题看懂样例就花了好久…
给一棵树,树上任意两个点的距离表示为距离%2,那这样任意两个点之间距离要不就是0要不就是1了,这样就能把树上的点分成两个集合,相同集合内点相距0,不同集合点相距1,然后推出公式就是 n + 6 ∗ ( C k 2 + C n − k 2 + C k 3 + C n − k 3 ) n+6*(C_k^2+C_{n-k}^2+C_k^3+C_{n-k}^3) n+6(Ck2+Cnk2+Ck3+Cnk3),所以问题就变成怎么把节点分开了,一开始就这个问题想了很多假算法,并查集用了一半发现不对,最后发现不就dfs就好了

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
typedef long long ll;
int n,u,v,w;
struct Edge{
   
    int v,w,next;
}edge[N*2];
int cnt,head[N];
int k;
ll c[N][5];
void init(){
   
    cnt=0;
    k=0;
    memset(head,-1,sizeof(head));
    c[1][1]=1;
    for(int i=1;i<=10005;i++){
   
        c[i][0]=1;
        for(int j=1;j<=3 && j<=i;j++){
   
            if(i==1 && j==1){
   
                continue;
            }
            c[i][j]=c[i-1][j]+c[i-1][j-1];
        }
    }
}
void addEdge(int u,int v,int w){
   
    edge[cnt]=Edge{
   v,w,head[u]};
    head[u]=cnt++;
    edge[cnt]=Edge{
   u,w,head[v]};
    head[v]=cnt++;
}
void dfs(int d,int u,int p){
   
    if(d%2==0){
   
        //printf("%d %d\n",u,d);
        k++;
    }
    for(int i=head[u];i!=-1;i=edge[i].next){
   
        int v=edge[i].v;
        int w=edge[i].w;
        if(v==p){
   
            continue;
        }
        dfs(d+w,v,u);
    }
}
int main(void){
   
    scanf("%d",&n);
    init();
    for(int i=0;i<n-1;i++){
   
        scanf("%d%d%d",&u,&v,&w);
        w%=2;
        addEdge(u,v,w);
    }
    dfs(0,1,-1);
    //printf("%d\n",k);
    ll ans=n;
    if(k>=2){
   
        ans+=6ll*c[k][2];
    }
    if(n-k>=2){
   
        ans+=6ll*c[n-k][2];
    }
    if(k>=3){
   
        ans+=6ll*c[k][3];
    }
    if(n-k>=3){
   
        ans+=6ll*c[n-k][3];
    }
    printf("%lld\n",ans);
    return 0;
}
全部评论

相关推荐

来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
那一天的Java_J...:他本来公司就是做这个的,不就是正常的游戏客户端和服务器开发,软硬件联动,有啥恶心不恶心的,提前告诉你就是怕你接受不了,接受不了就没必要再往后走流程浪费时间,虽然这公司是一坨。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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