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

    2
    |
4 - 1 - 3
    |
    5

int parent[N];
// parent[i] = j 表示节点 i 的父节点是 j

vector<int> adj[N];  // 无根树：存储所有相邻节点
vector<int> children[N];  // 有根树：只存储子节点

struct Node {
    int firstChild;   // 第一个子节点
    int nextSibling;  // 下一个兄弟节点
};

void dfs(int u, int from) {
    for (int v : adj[u]) {
        if (v != from) {
            dfs(v, u);
        }
    }
}

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

// 先序遍历：根 → 左 → 右
void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";  // 访问根
    preorder(root->left);       // 递归左子树
    preorder(root->right);      // 递归右子树
}

// 中序遍历：左 → 根 → 右
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);        // 递归左子树
    cout << root->val << " ";   // 访问根
    inorder(root->right);       // 递归右子树
}

// 后序遍历：左 → 右 → 根
void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);      // 递归左子树
    postorder(root->right);     // 递归右子树
    cout << root->val << " ";   // 访问根
}

void bfs(int root) {
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : children[u]) {
            q.push(v);
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> adj[N];
int dist[N], parent[N];

void dfs(int u, int fa, int d) {
    dist[u] = d;
    parent[u] = fa;
    for (int v : adj[u]) {
        if (v != fa) dfs(v, u, d + 1);
    }
}

int main() {
    int n;
    cin >> n;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 第一次 DFS
    dfs(1, -1, 0);
    int z = max_element(dist + 1, dist + n + 1) - dist;

    // 第二次 DFS
    dfs(z, -1, 0);
    int z2 = max_element(dist + 1, dist + n + 1) - dist;

    cout << "直径长度: " << dist[z2] << endl;

    // 输出直径路径
    vector<int> path;
    for (int u = z2; u != -1; u = parent[u]) {
        path.push_back(u);
    }
    // path 即为直径路径

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<pair<int,int>> adj[N]; // (邻点, 边权)
int d1[N], d2[N]; // 最长链、次长链
int diameter = 0;

void dp(int u, int fa) {
    d1[u] = d2[u] = 0;

    for (auto [v, w] : adj[u]) {
        if (v == fa) continue;

        dp(v, u);

        int d = d1[v] + w;
        if (d > d1[u]) {
            d2[u] = d1[u];
            d1[u] = d;
        } else if (d > d2[u]) {
            d2[u] = d;
        }
    }

    diameter = max(diameter, d1[u] + d2[u]);
}

int main() {
    int n;
    cin >> n;

    for (int i = 1; i < n; i++) {
        int u, v, w = 1;
        cin >> u >> v;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dp(1, -1);
    cout << "直径长度: " << diameter << endl;

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> adj[N];
int size_[N];      // 子树大小
int max_part[N];   // 删去该节点后的最大连通块
int n;
vector<int> centroids;

void dfs(int u, int fa) {
    size_[u] = 1;
    max_part[u] = 0;

    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u);
        size_[u] += size_[v];
        max_part[u] = max(max_part[u], size_[v]);
    }

    // 向上的连通块
    max_part[u] = max(max_part[u], n - size_[u]);

    // 判断是否为重心
    if (max_part[u] <= n / 2) {
        centroids.push_back(u);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, -1);

    cout << "重心: ";
    for (int c : centroids) {
        cout << c << " ";
    }
    cout << endl;

    return 0;
}

dp[v] = dp[u] + n - 2 * size[v];

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> adj[N];
int n, size_[N], dep[N];
long long dp[N];  // dp[u] = 以u为根的距离和

void dfs1(int u, int fa) {
    size_[u] = 1;
    dp[u] = dep[u];  // 初始值：当前节点对根的距离贡献 = 深度
    for (int v : adj[u]) {
        if (v == fa) continue;
        dep[v] = dep[u] + 1;  // 先传递深度
        dfs1(v, u);           // 递归子节点
        size_[u] += size_[v]; // 累加子树大小
        dp[u] += dp[v];       // 累加子节点对根的距离贡献
    }
}

void dfs2(int u, int fa) {
    for (int v : adj[u]) {
        if (v == fa) continue;
        // 换根转移公式：dp[v] = dp[u] + n - 2*size[v]
        dp[v] = dp[u] - size_[v] + (n - size_[v]);
        dfs2(v, u);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dep[1] = 0;  // 根节点深度为0
    dfs1(1, -1); // 第一次DFS：计算size和dp[根]
    dfs2(1, -1); // 第二次DFS：换根转移，计算所有dp值

    // 距离和最小的节点即为重心
    int centroid = min_element(dp + 1, dp + n + 1) - dp;
    cout << "重心: " << centroid << endl;
    cout << "距离和: " << dp[centroid] << endl;

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int parent[N], rank_[N];

// 并查集查找（带路径压缩）
int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

// 并查集合并（按秩合并）
bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (rank_[x] < rank_[y]) swap(x, y);
    parent[y] = x;
    if (rank_[x] == rank_[y]) rank_[x]++;
    return true;
}

struct Edge {
    int u, v, w;
    bool operator<(const Edge& e) const { return w < e.w; }
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    // 初始化并查集
    for (int i = 1; i <= n; i++) parent[i] = i;

    // Kruskal
    sort(edges.begin(), edges.end());
    int totalWeight = 0, edgeCount = 0;

    for (auto& e : edges) {
        if (unite(e.u, e.v)) {
            totalWeight += e.w;
            edgeCount++;
            cout << "选中边: " << e.u << " - " << e.v
                 << " (权重 " << e.w << ")" << endl;
            if (edgeCount == n - 1) break;
        }
    }

    if (edgeCount == n - 1) {
        cout << "最小生成树总权重: " << totalWeight << endl;
    } else {
        cout << "图不连通，无法生成最小生成树" << endl;
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
const int INF = 1e9;

int n, m;
vector<pair<int, int>> adj[N]; // (邻点, 边权)
int minDist[N];   // 到已选集合的最小距离
int parent[N];    // 记录生成树的父节点
bool inMST[N];

int prim(int start) {
    fill(minDist, minDist + n + 1, INF);
    fill(inMST, inMST + n + 1, false);
    fill(parent, parent + n + 1, -1);

    minDist[start] = 0;
    int totalWeight = 0;

    for (int i = 0; i < n; i++) {
        // 找最小距离的未选节点
        int u = -1, minD = INF;
        for (int v = 1; v <= n; v++) {
            if (!inMST[v] && minDist[v] < minD) {
                minD = minDist[v];
                u = v;
            }
        }

        if (u == -1) break; // 图不连通

        inMST[u] = true;
        totalWeight += minDist[u];

        if (parent[u] != -1) {
            cout << "选中边: " << parent[u] << " - " << u
                 << " (权重 " << minDist[u] << ")" << endl;
        }

        // 更新邻接节点的最小距离
        for (auto [v, w] : adj[u]) {
            if (!inMST[v] && w < minDist[v]) {
                minDist[v] = w;
                parent[v] = u;
            }
        }
    }

    return totalWeight;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    int totalWeight = prim(1);
    cout << "最小生成树总权重: " << totalWeight << endl;

    return 0;
}

int prim_heap(int start) {
    fill(minDist, minDist + n + 1, INF);
    fill(inMST, inMST + n + 1, false);

    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>> pq;

    minDist[start] = 0;
    pq.push({0, start});
    int totalWeight = 0, cnt = 0;

    while (!pq.empty() && cnt < n) {
        auto [d, u] = pq.top(); pq.pop();

        if (inMST[u]) continue;
        inMST[u] = true;
        totalWeight += d;
        cnt++;

        for (auto [v, w] : adj[u]) {
            if (!inMST[v] && w < minDist[v]) {
                minDist[v] = w;
                parent[v] = u;
                pq.push({w, v});
            }
        }
    }

    return totalWeight;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+5;

ll n, s, tot, hd[N], cnt, dis[N], ans=9999999999, top, k, fa[N], line[N];
struct edge { ll t, nxt, va; } es[N<<2];

// 快读快写模板
template <typename T> void rd(T &x) {
    ll fl=1; x=0; char c=getchar();
    for(; !isdigit(c); c=getchar()) if(c=='-') fl=-fl;
    for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    x*=fl;
}

void add(ll u, ll v, ll w) {
    es[++tot] = (edge){v, hd[u], w}, hd[u] = tot;
}

// DFS求最远点，同时记录父亲
void dfs(ll x, ll ff) {
    fa[x] = ff;
    if(dis[x] > dis[k]) k = x;  // 更新最远点
    for(ll i = hd[x]; i; i = es[i].nxt) {
        ll to = es[i].t;
        if(to == ff || line[to]) continue;  // 跳过父亲和已标记的直径节点
        dis[to] = dis[x] + es[i].va;
        dfs(to, x);
    }
}

int main() {
    rd(n); rd(s);
    for(ll i=1, u, v, w; i<n; i++) {
        rd(u); rd(v); rd(w);
        add(u, v, w); add(v, u, w);
    }

    // 第一步：求直径
    dis[1] = 1; dfs(1, 0);       // 第一次DFS：从任意点找最远点k
    dis[k] = 0; dfs(k, 0);       // 第二次DFS：从k找最远点top
    top = k;                     // top是直径的另一端点

    // 第二步：尺取法在直径上找最优路径
    for(ll i=top, j=top; i; i=fa[i]) {
        // i从top向另一端移动，j跟随移动保证路径长度<=s
        while(dis[j] - dis[i] > s) j = fa[j];
        // 更新答案：偏心距 = max(左端距离, 右端距离)
        ans = min(ans, max(dis[i], dis[top] - dis[j]));
    }

    // 第三步：标记直径上的节点
    for(ll i=top; i; i=fa[i]) line[i] = 1;

    // 第四步：计算直径外分支的最大深度
    for(ll i=top; i; i=fa[i]) {
        k = i; dis[k] = 0;
        dfs(i, fa[i]);  // 从直径节点出发DFS其分支
    }

    // 最终答案：取所有节点到路径的最大距离
    for(ll i=1; i<=n; i++) ans = max(ans, dis[i]);

    printf("%lld\n", ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;

const int N = 1e5 + 1;
int MOD, n;

vector<ii> adj[N];
int subsize[N];
bool visited[N];
int treesize;
vi clrlist;
ll up[N], down[N];
int h[N];
int PHI;
int dppart[N];

// 快速幂
ll modpow(ll a, ll b) {
    ll r = 1;
    while(b) {
        if(b&1) r = (r*a) % MOD;
        a = (a*a) % MOD;
        b >>= 1;
    }
    return r;
}

ll mult(ll a, ll b) { return (a*b) % MOD; }
ll add(ll a, ll b) { return (a+b+MOD) % MOD; }

ll inv(ll a) { return modpow(a, PHI-1); }  // 模逆元

// 欧拉函数（用于求逆元）
int phi(int n) {
    ll num = 1, num2 = n;
    for(ll i = 2; i*i <= n; i++) {
        if(n % i == 0) {
            num2 /= i;
            num *= (i-1);
        }
        while(n % i == 0) n /= i;
    }
    if(n > 1) { num2 /= n; num *= (n-1); }
    return num * num2;
}

// 计算子树大小
void dfs(int u, int par) {
    if(par == -1) clrlist.clear();
    subsize[u] = 1;
    clrlist.pb(u);
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i].fi;
        if(visited[v] || v == par) continue;
        dfs(v, u);
        subsize[u] += subsize[v];
    }
    if(par == -1) treesize = subsize[u];
}

// 找重心
int centroid(int u, int par) {
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i].fi;
        if(visited[v] || v == par) continue;
        if(subsize[v]*2 > treesize) return centroid(v, u);
    }
    return u;
}

// 计算各节点的up、down、h值
int parts = 0;
void fill(int u, int p, int cent) {
    if(p == cent) {
        dppart[u] = parts;
        parts++;
    } else if(p != -1) {
        dppart[u] = dppart[p];
    }
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i].fi, w = adj[u][i].se;
        if(v == p || visited[v]) continue;
        down[v] = add(mult(down[u], 10), w);
        up[v] = add(up[u], mult(modpow(10, h[u]), w));
        h[v] = h[u] + 1;
        fill(v, u, cent);
    }
}

// 统计经过cent的满足条件的路径数
ll solve(int cent) {
    for(int u : clrlist) { up[u] = 0; down[u] = 0; h[u] = 0; }
    parts = 0;
    fill(cent, -1, cent);
    parts--;
    dppart[cent] = -1;

    map<ll,ll> tot;  // 所有up值的统计
    vector<map<ll,ll>> vec(parts+1);  // 各子树up值统计
    tot[0]++;
    for(int u : clrlist) {
        if(u == cent) continue;
        tot[up[u]]++;
        vec[dppart[u]][up[u]]++;
    }

    ll ans = 0;
    for(int u : clrlist) {
        int ht = h[u], pt = dppart[u];
        if(u == cent) {
            ans += (tot[0] - 1);  // cent作为起点
        } else {
            ll val = mult((-down[u]) % MOD + MOD, inv(modpow(10, ht)));
            ans += (tot[val] - vec[pt][val]);  // 减去同一子树内的
        }
    }
    return ans;
}

// 点分治主过程
ll compsolve(int u) {
    dfs(u, -1);
    int cent = centroid(u, -1);
    ll ans = solve(cent);
    visited[cent] = true;
    for(int i = 0; i < adj[cent].size(); i++) {
        int v = adj[cent][i].fi;
        if(!visited[v]) ans += compsolve(v);
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> MOD;
    if(MOD == 1) {
        cout << ll(n) * ll(n-1) << '\n';
        return 0;
    }
    PHI = phi(MOD);  // 欧拉函数值
    for(int i = 0; i < n-1; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].pb(ii(v, w)); adj[v].pb(ii(u, w));
    }
    cout << compsolve(0) << '\n';
    return 0;
}