高中生程式解題系統

#20306: 終於AC了，TLE的請進，沒想法的也請進，樹的新手也可請進

superuserjoy@gmail.com (summeruserjoy)

學校 : 國立中興大學
編號 : 98294
來源 : [49.217.239.47]
最後登入時間：
2022-04-05 21:11:31

b967. 4. 血緣關係 -- 2016年3月 apcs | From: [180.204.210.235] | 發表日期 : 2019-12-27 11:03

如果輕微TLE，可先服用這帖：http://chino.taipei/note-2016-0311C-%E7%9A%84%E8%BC%B8%E5%87%BA%E5%85%A5cin-cout%E5%92%8Cscanf-printf%E8%AA%B0%E6%AF%94%E8%BC%83%E5%BF%AB%EF%BC%9F/

重度TLE，請先優化你的遞迴、演算法、遍歷，不要一個Node經過好幾次，可用深度優先避免重複經過

深度優先：http://www.csie.ntnu.edu.tw/~u91029/Graph.html#7

樹的部分由樹根、節點、樹葉構成

沒有parent的節點可以判斷為root

沒有child的節點可以判斷為leaf

而每一個節點(node)的屬性我就定義一個struct，裡面有parent、child、還有本題蠻需要的子樹高度(最大和第二大高度相加有機率是最佳解)

接下來就是程式碼啦~不要直接抄，變數還有屬性名稱我都定義清楚了，沒想法看個想法回去自己寫~~

呼應解鎖運動，貼碼!

#include <iostream>
#include <vector>
using namespace std;
struct Node{
  int parent=-1;
  vector<int> child;
  int height[2]={0,0};
  
};
vector<Node> node;
int maxdis(int id){
  if(node[id].child.size()==0){
    return(0);
  }
  else{
    int maxresult=0,maxlength;
    for(int i = 0;i < node[id].child.size();i++){
      int height,result;
      result=maxdis(node[id].child[i]);
      height=node[node[id].child[i]].height[0]+1;
      if(height>node[id].height[0]){
        swap(node[id].height[0],node[id].height[1]);
        node[id].height[0]=height;

      }
      else if(height>node[id].height[1]){
        node[id].height[1]=height;
      }
      if(result>maxresult){
        maxresult=result;
      }
      
        
    }
    maxlength=node[id].height[0]+node[id].height[1];
    if(maxresult>maxlength){
      return(maxresult);
    }
    else{
      return(maxlength);
    }
  }
}
int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int N;
  while(cin>>N){
    node.resize(0);
    node.resize(N);

    for(int i = 0;i<N-1;i++){
      int parent,child;
      cin>>parent>>child;
      node[parent].child.push_back(child);
      node[child].parent=parent;      
    }
    int root=0;
    while(node[root].parent!=-1){
      root=node[root].parent;
    }
    if(root==N)
      root-=1;
    cout<<maxdis(root)<<"\n";
    
    
  }
}

| 回應文章 | 回原始文章

#20307: Re:終於AC了，TLE的請進，沒想法的也請進，樹的新手也可請進

superuserjoy@gmail.com (summeruserjoy)

學校 : 國立中興大學
編號 : 98294
來源 : [49.217.239.47]
最後登入時間：
2022-04-05 21:11:31

b967. 4. 血緣關係 -- 2016年3月 apcs | From: [180.204.210.235] | 發表日期 : 2019-12-27 11:16

如果輕微TLE，可先服用這帖：http://chino.taipei/note-2016-0311C-%E7%9A%84%E8%BC%B8%E5%87%BA%E5%85%A5cin-cout%E5%92%8Cscanf-printf%E8%AA%B0%E6%AF%94%E8%BC%83%E5%BF%AB%EF%BC%9F/

重度TLE，請先優化你的遞迴、演算法、遍歷，不要一個Node經過好幾次，可用深度優先避免重複經過

深度優先：http://www.csie.ntnu.edu.tw/~u91029/Graph.html#7

樹的部分由樹根、節點、樹葉構成

沒有parent的節點可以判斷為root

沒有child的節點可以判斷為leaf

而每一個節點(node)的屬性我就定義一個struct，裡面有parent、child、還有本題蠻需要的子樹高度(最大和第二大高度相加有機率是最佳解)

接下來就是程式碼啦~不要直接抄，變數還有屬性名稱我都定義清楚了，沒想法看個想法回去自己寫~~

呼應解鎖運動，貼碼!

#include <iostream>
#include <vector>
using namespace std;
struct Node{
  int parent=-1;
  vector<int> child;
  int height[2]={0,0};
  
};
vector<Node> node;
int maxdis(int id){
  if(node[id].child.size()==0){
    return(0);
  }
  else{
    int maxresult=0,maxlength;
    for(int i = 0;i < node[id].child.size();i++){
      int height,result;
      result=maxdis(node[id].child[i]);
      height=node[node[id].child[i]].height[0]+1;
      if(height>node[id].height[0]){
        swap(node[id].height[0],node[id].height[1]);
        node[id].height[0]=height;

      }
      else if(height>node[id].height[1]){
        node[id].height[1]=height;
      }
      if(result>maxresult){
        maxresult=result;
      }
      
        
    }
    maxlength=node[id].height[0]+node[id].height[1];
    if(maxresult>maxlength){
      return(maxresult);
    }
    else{
      return(maxlength);
    }
  }
}
int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int N;
  while(cin>>N){
    node.resize(0);
    node.resize(N);

    for(int i = 0;i<N-1;i++){
      int parent,child;
      cin>>parent>>child;
      node[parent].child.push_back(child);
      node[child].parent=parent;      
    }
    int root=0;
    while(node[root].parent!=-1){
      root=node[root].parent;
    }
    if(root==N)
      root-=1;
    cout<<maxdis(root)<<"\n";
    
    
  }
}

覺得我的程式有地方可以優化的也可以mail喔~希望大家能夠互相建議，把程式越寫越好，有問題也歡迎mail我

| 回應文章 | 回原始文章

#20308: Re:終於AC了，TLE的請進，沒想法的也請進，樹的新手也可請進

asnewchien@gmail.com (david)

學校 : 不指定學校
編號 : 68108
來源 : [114.42.132.249]
最後登入時間：
2024-05-07 23:09:03

b967. 4. 血緣關係 -- 2016年3月 apcs | From: [111.246.63.52] | 發表日期 : 2019-12-27 13:05

不要貼答案啦。

| 回應文章 | 回原始文章

#35058: Re: 終於AC了，TLE的請進，沒想法的也請進，樹的新手也可請進

yp11151128@yphs.tp.edu.tw (80833)

學校 : 臺北市私立延平高級中學
編號 : 225479
來源 : [203.72.178.1]
最後登入時間：
2024-01-15 11:29:52

b967. 4. 血緣關係 -- 2016年3月 apcs | From: [203.72.178.1] | 發表日期 : 2023-05-05 08:29

如果輕微TLE，可先服用這帖：http://chino.taipei/note-2016-0311C-%E7%9A%84%E8%BC%B8%E5%87%BA%E5%85%A5cin-cout%E5%92%8Cscanf-printf%E8%AA%B0%E6%AF%94%E8%BC%83%E5%BF%AB%EF%BC%9F/

重度TLE，請先優化你的遞迴、演算法、遍歷，不要一個Node經過好幾次，可用深度優先避免重複經過

深度優先：http://www.csie.ntnu.edu.tw/~u91029/Graph.html#7

樹的部分由樹根、節點、樹葉構成

沒有parent的節點可以判斷為root

沒有child的節點可以判斷為leaf

而每一個節點(node)的屬性我就定義一個struct，裡面有parent、child、還有本題蠻需要的子樹高度(最大和第二大高度相加有機率是最佳解)

接下來就是程式碼啦~不要直接抄，變數還有屬性名稱我都定義清楚了，沒想法看個想法回去自己寫~~

呼應解鎖運動，貼碼!
#include <iostream>
#include <vector>
using namespace std;
struct Node{
  int parent=-1;
  vector<int> child;
  int height[2]={0,0};
  
};
vector<Node> node;
int maxdis(int id){
  if(node[id].child.size()==0){
    return(0);
  }
  else{
    int maxresult=0,maxlength;
    for(int i = 0;i < node[id].child.size();i++){
      int height,result;
      result=maxdis(node[id].child[i]);
      height=node[node[id].child[i]].height[0]+1;
      if(height>node[id].height[0]){
        swap(node[id].height[0],node[id].height[1]);
        node[id].height[0]=height;

      }
      else if(height>node[id].height[1]){
        node[id].height[1]=height;
      }
      if(result>maxresult){
        maxresult=result;
      }
      
        
    }
    maxlength=node[id].height[0]+node[id].height[1];
    if(maxresult>maxlength){
      return(maxresult);
    }
    else{
      return(maxlength);
    }
  }
}
int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int N;
  while(cin>>N){
    node.resize(0);
    node.resize(N);

    for(int i = 0;i<N-1;i++){
      int parent,child;
      cin>>parent>>child;
      node[parent].child.push_back(child);
      node[child].parent=parent;      
    }
    int root=0;
    while(node[root].parent!=-1){
      root=node[root].parent;
    }
    if(root==N)
      root-=1;
    cout<<maxdis(root)<<"\n";
    
    
  }
}
覺得我的程式有地方可以優化的也可以mail喔~希望大家能夠互相建議，把程式越寫越好，有問題也歡迎mail我

你要不要在修改一下你發出來的碼，我貼完碼後第四個還是TLE

| 回應文章 | 回原始文章

#36062: Re: 終於AC了，TLE的請進，沒想法的也請進，樹的新手也可請進

vic20050418@gmail.com (Wen Vic)

學校 : 國立臺灣科技大學
編號 : 153262
來源 : [114.136.159.95]
最後登入時間：
2023-07-29 13:10:41

b967. 4. 血緣關係 -- 2016年3月 apcs | From: [114.136.165.80] | 發表日期 : 2023-07-02 23:51

如果輕微TLE，可先服用這帖：http://chino.taipei/note-2016-0311C-%E7%9A%84%E8%BC%B8%E5%87%BA%E5%85%A5cin-cout%E5%92%8Cscanf-printf%E8%AA%B0%E6%AF%94%E8%BC%83%E5%BF%AB%EF%BC%9F/

重度TLE，請先優化你的遞迴、演算法、遍歷，不要一個Node經過好幾次，可用深度優先避免重複經過

深度優先：http://www.csie.ntnu.edu.tw/~u91029/Graph.html#7

樹的部分由樹根、節點、樹葉構成

沒有parent的節點可以判斷為root

沒有child的節點可以判斷為leaf

而每一個節點(node)的屬性我就定義一個struct，裡面有parent、child、還有本題蠻需要的子樹高度(最大和第二大高度相加有機率是最佳解)

接下來就是程式碼啦~不要直接抄，變數還有屬性名稱我都定義清楚了，沒想法看個想法回去自己寫~~

呼應解鎖運動，貼碼!
#include <iostream>
#include <vector>
using namespace std;
struct Node{
  int parent=-1;
  vector<int> child;
  int height[2]={0,0};
  
};
vector<Node> node;
int maxdis(int id){
  if(node[id].child.size()==0){
    return(0);
  }
  else{
    int maxresult=0,maxlength;
    for(int i = 0;i < node[id].child.size();i++){
      int height,result;
      result=maxdis(node[id].child[i]);
      height=node[node[id].child[i]].height[0]+1;
      if(height>node[id].height[0]){
        swap(node[id].height[0],node[id].height[1]);
        node[id].height[0]=height;

      }
      else if(height>node[id].height[1]){
        node[id].height[1]=height;
      }
      if(result>maxresult){
        maxresult=result;
      }
      
        
    }
    maxlength=node[id].height[0]+node[id].height[1];
    if(maxresult>maxlength){
      return(maxresult);
    }
    else{
      return(maxlength);
    }
  }
}
int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int N;
  while(cin>>N){
    node.resize(0);
    node.resize(N);

    for(int i = 0;i<N-1;i++){
      int parent,child;
      cin>>parent>>child;
      node[parent].child.push_back(child);
      node[child].parent=parent;      
    }
    int root=0;
    while(node[root].parent!=-1){
      root=node[root].parent;
    }
    if(root==N)
      root-=1;
    cout<<maxdis(root)<<"\n";
    
    
  }
}
覺得我的程式有地方可以優化的也可以mail喔~希望大家能夠互相建議，把程式越寫越好，有問題也歡迎mail我
你要不要在修改一下你發出來的碼，我貼完碼後第四個還是TLE

題目被改過了啦==

根本過不了

| 回應文章 | 回原始文章

ZeroJudge Forum