c++ - 计算单值子树

Question

在最近的 Codechef 竞赛中，我必须编写一个程序来计算给定树中单值子树的数量。如果子树的所有节点都具有相同的值，则子树是单值的。

在输入中，节点编号为 0 到 N-1。每个节点包含一个整数值。每个节点可以有任意数量的到其他节点的边。总共有 N-1 条边。树总是以节点 0 为根。

我写了下面的代码:

struct Node {
    int data;
    vector<unsigned> edge; //stores the node number of each child node
};

//i know these really shouldn't be global
unsigned long long count = 0;
vector<Node> tree;

//n is the number of the node at which the tree is rooted
//initally we call isUnivalued(0)
bool isUnivalued(unsigned n) {
    if(tree[n].edge.size() == 0){
        count++;
        return true; //leaves are univalued
    }
    bool allUnivalued = true;
    for(auto i : tree[n].edge)
        if(!isUnivalued(i))
            allUnivalued = false;
    if(!allUnivalued)
        return false;
    for(auto i : tree[n].edge)
        if(tree[i].data != tree[n].data)
            return false;
    count++;
    return true;
}

这为我尝试过的所有小测试用例提供了正确答案。但是当我提交问题时，法官发现某些测试用例的答案不正确。

我正在寻找一些帮助来弄清楚在什么情况下这可能会失败以及为什么会失败。

编辑:例子

  0
 / \
0   1
   / \
  1   1

这里的答案应该是 4。虽然最大的子树(整棵树本身)不是单值的，但所有其他子树都是。 假设所有节点的值为 1，则答案为 5。

Answer 1

• 在进入重点之前，让我向您推荐一个很好的方法来检查您提交的长测试用例，而无需使用 pen&paper。

首先，尝试找出一种并行执行 native 代码的替代方法，同时比较给定的结果

直到遇到条件断点，然后检查它。

其次，在同时运行两种不同的方法后，结果没有这样的差异，这意味着你的方法的各个方面

除了一个异常(exception)，这是一个最终的 stack overflow在可能引起内存过载的重复过多调用之后。

考虑将结构化树作为输入(虽然，我不确定应该如何将输入引入系统)

tree[0] , tree[1]  , tree[2]  , tree[3]  ,..., tree[k-1], tree[k]  , tree[k+1],  tree[n]   ,...  
        |          |          |          |...|          |          |          |            |... 
{v1,1,n}|{v2,2,n-1}|{v3,3,n-2}|{v4,4,n-3}|...|{vk,k,k+1}|{vk+1,0,0}|{vk+2,0,0}|{vn+1,n+2,L}|...

tree[k]和tree[k+1]是叶子，栈的结构如下...

v1,v2,V3,V4,...vk,vk+1,-1,vk+2,-1,-1,vk+3,...

这棵树vesiting是单线程的，意味着它是线性计算。

举个例子:

级别=0，计数=0。

1      ,1      ,1      ,1      ,-1     ,1      ,-1     ,-1     ,0    (data changed),-1     ,-1     ,1      .
level=0,level=1,level=2,level=3,level--,level=3,level--,level--,reset(level)level=1,level--,level=0,reset(level=1) (data changed)
count=1,count=2,count=3,count=4,count=4,count=5,.......,.......,count=count-level+1,count=4,.......,count=count-0+1=5 (data changed)

树:

            --------1-------        
           -----1----       1   
          --- 1---    0
          1       1        

等级:

            --------0-------        
           -----1----       1   
          --- 2---    1
          3       3        

计数:

            --------1-------        
           -----2----       5   
          --- 3---    4
          4       5        

子树数量:5

            --------1-------        
           -----1----       *   
          --- *---    *
          *       *        

---

-剩下的情况(树索引困惑且结构错误)，这里是如何验证我的，以及您的算法，

查看数值和计时结果:

代码:

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <time.h>
using namespace std;

struct Node {
int data;
int *edge ; //stores the node number of each child node
};
// Yes they are global variables
vector<int> stack;
vector<Node> tree;
vector<int*>callstack;


void fillwithrandom(int *n,int *m,int count)
{
int a;
Node T;
T.data=rand()%2;T.edge=&(*(int*)malloc(3*sizeof(int))=3);
tree.push_back(T);
stack.push_back(T.data);
if ((a=rand()%count)!=0)
   fillwithrandom(&(*n=(T.edge[1]=++(*n))),&(++(*m)),a);
else return stack.push_back((T.edge[0]=0)-++(*m));  


while ((a=rand()%count)==0);
fillwithrandom(&(*n=(T.edge[2]=++(*n))),&(++(*m)),a);

stack.push_back(-++(*m));
}


void iterativetree( int* m){

int level=0,lasti,previouslevel=0,stackk;
callstack.clear();




callstack.push_back(&(*(int*)malloc(2*sizeof(int))=0));stackk=(lasti=tree[callstack[0][1]=0].data);
for (int j=0;j>=0;){


if (stackk>=0)

        if ((lasti&1)==(stackk&1))
          {(*m)++;(level)++;lasti=stackk;}
        else
        {*m=*m-level+1;previouslevel=level;level=1;lasti=stackk;}
else 
(level)-=!!level;


if (++callstack[j][1]==tree[callstack[j][0]].edge[0]|tree[callstack[j][0]].edge[0]==0)
    {callstack.pop_back();j--;stackk=-1;}
    else 
    {callstack.push_back(&(*(int*)malloc(2*sizeof(int))=tree[callstack[j][0]].edge[callstack[j][1]]));
    j++;callstack[j][1]=0;stackk=tree[callstack[j][0]].data;};

}



}





int main(){
double count=0 ;
int a,b,c,d;

while(1){
tree.clear();callstack.clear();

tree.reserve(c=rand());
callstack.reserve(c);

// filling with random values    
fillwithrandom(&(a=0),&(b=0),c);
stack[b]--;

iterativetree(&(a=0));


printf(" %d univalued subtrees",a);printf("\n ");
system("pause"); 
}
}

online comparison