P3304

• 大体思路
• code

大体思路

1. 第一遍 dfs 找到最远点
2. 第二遍 dfs 找到直径，及直径的中点。
3. 分情况讨论，
   3.1. 当直径中点在一条边时，分裂成两树：对边的两点进行dfs找到 maxdeep
   3.2. 当直径中点在一个点时，对点的child找到maxdeep最长的两个，然后分裂成2棵树
   3.3. 被分裂的树中，如果树的root的maxdeep的child只有一个，那么共直径的边数量就+1
   

code

#include <iostream>
#include <cassert>
#include <iomanip>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <climits>
#include <functional>
#include <list>
#include <cstdlib>
#include <set>
#include <stack>
#include <sstream>
#include <numeric>
#include <map>
#include <algorithm>
#include <bitset>

#define endl "\n"
#define i64 long long
#define ui64 unsigned long long
#define INF 0x3f3f3f3f
#define MZ(arr) memset(arr,0,sizeof(arr))
#define MS(arr,val) memset(arr,val,sizeof(arr))

//浮点数输出保留小数点多少位
//cout << setiosflags(ios::fixed) << setprecision(2);

using namespace std;

namespace Buffalo{
struct HeadNxtG{
  vector<int> head;
  vector<int> ver;
  vector<int> nxt;
  vector<int> wi;
  int tot;

  HeadNxtG(int nodeLen,int edgeLen){
    head.resize(nodeLen);
    ver.resize(edgeLen<<1);
    nxt.resize(edgeLen<<1);
    wi.resize(edgeLen<<1);
    deep.resize(nodeLen);
    maxDeep.resize(nodeLen);
    parents.resize(nodeLen);
    parentswi.resize(nodeLen);
    tot=0;
  }

  void add(int u,int v,int w){
    ver[++tot] = v;
    nxt[tot] = head[u];
    head[u] = tot;
    wi[tot] = w;
  }

  void addE(int u,int v,int w){
    add(u,v,w);
    add(v,u,w);
  }

  i64 maxLen;
  int q;
  vector<i64> deep;
  vector<i64> maxDeep;
  vector<int> parents;
  vector<i64> parentswi;
  void findMaxLen() {
      maxLen = 0; q = 0;
      dfs(1, 0);
      deep[q] = 0;
      maxLen = 0;
      dfs2(q, 0);
      i64 midLen = maxLen / 2;
      i64 findParentLen = 0;
      int preq;
      while (findParentLen < midLen) {
          findParentLen += parentswi[q];
          preq = q;
          q = parents[q];
      }
      
      deep.assign(head.size(), 0);
      //一个点分成两棵树
      if (findParentLen == midLen) {
          dfs3(q, 0);
          i64 maxV = 0;
          int maxVcnt = 1;
          for (int e = head[q]; e > 0; e = nxt[e]) {
              if (maxV <= maxDeep[ver[e]]) {
                  if (maxV < maxDeep[ver[e]]) maxV = maxDeep[ver[e]];
                  else maxVcnt++;
              } 
          }
          if (maxVcnt != 2) {
              cout << maxLen << endl << 0 << endl;
              return;
          }

          int twochild1=0;
          int twochild2=0;
          for (int e = head[q]; e > 0; e = nxt[e]) {
              if (maxV == maxDeep[ver[e]]) {
				  if (twochild1 == 0) twochild1 = ver[e];
				  else twochild2 = ver[e];
              } 
          }
          int ret = findCnt(twochild1, q);
          ret += findCnt(twochild2, q);
		  cout << maxLen << endl << ret << endl;
      } else {
          dfs3(q, preq);
          dfs3(preq,q);
          int ret = findCnt(q, preq) + 1;
          ret += findCnt(preq, q);
		  cout << maxLen << endl << ret << endl;
      }
  }
  //查找直径未分裂的数量
  int findCnt(int u, int fa) {
      i64 maxCDeep = 0;
      int cnt = 0;
      int maxV = 0;
      for (int e = head[u]; e > 0; e = nxt[e]) {
          int v = ver[e];
          if (v != fa) {
              if (maxDeep[v] > maxCDeep) {
                  maxCDeep = maxDeep[v];
                  maxV = v;
              }
          }
      }
      for (int e = head[u]; e > 0; e = nxt[e]) {
          int v = ver[e];
          if (v != fa) {
              if (maxDeep[v] == maxCDeep) {
                  cnt++;
              }
          }
      }
      if (cnt == 1 && maxV > 0) {
          return 1 + findCnt(maxV, u);
      }
      return 0;
  }
  //求maxdeep
  void dfs3(int u, int fa) {
      maxDeep[u] = deep[u];
      for (int e = head[u]; e > 0; e = nxt[e]) {
          int v = ver[e];
          int w = wi[e];
          if (v != fa) {
              deep[v] = deep[u] + w;
              dfs3(v, u);
              maxDeep[u] = max(maxDeep[u], maxDeep[v]);
          }
      }
  }
  //最远点查找最远点,并求出直径长度及路径
  void dfs2(int u, int fa) {
      for (int e = head[u]; e > 0; e = nxt[e]) {
          int v = ver[e];
          int w = wi[e];
          if (v != fa) {
              deep[v] = deep[u] + w;
              parents[v] = u;
              parentswi[v] = w;
              if (maxLen < deep[v]) {
                  maxLen = deep[v];
                  q = v;
              }
              dfs2(v, u);
          }
      }
  }
  //任一点查找最远点
  void dfs(int u, int fa) {
      for (int e = head[u]; e > 0; e = nxt[e]) {
          int v = ver[e];
          int w = wi[e];
          if (v != fa) {
              deep[v] = deep[u] + w;
              if (maxLen < deep[v]) {
                  maxLen = deep[v];
                  q = v;
              }
              dfs(v, u);
          }
      }
  }
};
}

namespace SLOVER {

#define NMAX 100005

    void slove() {
        i64 maxLen = 0;
        int q;
        int n;
        cin >> n;
        Buffalo::HeadNxtG hng(n + 1, n + 1);
        int u, v, w;
        for (int i = 1; i < n; ++i) {
            cin >> u >> v >> w;
            hng.addE(u, v, w);
        }
        hng.findMaxLen();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int  t = 1;
    while (t--) { SLOVER::slove(); }
    return 0;
}