虽然官方解释是这题目里的树看作无向无环图，从答案来看还是在“以1作为根节点”这一前提下进行的，这棵树搭建好以后，从叶节点开始访问，一直推到根节点即可——很像动态规划的“自底向上”。

但这棵树的搭建堪忧：给出的边不知道哪边更接近根节点。所以我给出的方案干脆在两个顶点都将对方加成孩子，等到访问的时候再作处理，根据从1这个根节点开始访问这个特性，额外加一个“isVisited"来做区分。

然后利用栈对树进行非递归访问

/** * For best-coder problem 3 */#include 
     
      using namespace std;#include 
      
       #include 
       
        struct Node{public:    Node() :mIsVisited(false) {}    bool mIsVisited;    set< int > mChilds;    set< int > mColorSet;};int main(){    int nNode, nCounting;    while( cin >> nNode >> nCounting )    {        Node node[50001];        for( int i=1; i
        
         > a >> b;            node[a].mChilds.insert(b);            node[b].mChilds.insert(a);        }        for( int i=0; i
         
          > n >> color;            node[n].mColorSet.insert(color);        }        stack
          
            nodeStack; node[1].mIsVisited = true; nodeStack.push(1); do{ int currentTop = nodeStack.top(); Node& topNode = node[currentTop]; set
           
             & topChilds = topNode.mChilds; set
            
              & topColors = topNode.mColorSet; for( set
             
              ::iterator ci = topChilds.begin(); ci != topChilds.end(); ci++ ) { int child = *ci; if( node[child].mIsVisited ) { topChilds.erase(child); continue; } node[child].mIsVisited = true; nodeStack.push(child); break; } // it's a leaf child if( topChilds.empty() ) { nodeStack.pop(); if( nodeStack.empty() ) continue; Node& topNode = node[ nodeStack.top() ]; topNode.mColorSet.insert(topColors.begin(),topColors.end()); topNode.mChilds.erase(currentTop); continue; } }while(!nodeStack.empty()); // output for( int i=1; i<=nNode; i++ ) { cout << node[i].mColorSet.size(); if( i != nNode ) { cout << " "; }else{ cout << endl; } } }}