点分治适合处理大规模的树上路径信息问题。
题意：给定一棵有 n n n 个点的带点权树， m m m 次询问，每次询问给出 k k k，询问树上距离为 k k k 的点对是否存在。
#include<bits/stdc++.h> using namespace std; //#define endl '\n' #define IOS ios::sync_with_stdio(false); cin.tie(0), cout.tie(0) typedef long long LL; using PII = pair<int, int>; const int N = 1e4 + 5, V = 1e7 + 5; vector<PII> G[N]; int n, m, rt, cnt, masz, tot, que[105], ans[105], siz[N], dis[N], dd[N]; /* rt当前子树的重心（最大子树最小） tot当前子树的大小 */ bool vis[N], flag[V]; void dfsize(int v, int p){ // 找树跟，获得所有子树的大小 siz[v] = 1; int ms = 0; for(PII e : G[v]){ if(e.first == p || vis[e.first])continue; dfsize(e.first, v); siz[v] += siz[e.first]; ms = max(ms, siz[e.first]); } ms = max(ms, tot - siz[v]); if(masz > ms)masz = ms, rt = v; } void getdis(int v, int p){ // 获得子树内的各点到rt的距离 dd[++cnt] = dis[v]; for(PII e : G[v]){ if(e.first == p || vis[e.first])continue; dis[e.first] = dis[v] + e.second; getdis(e.first, v); } } void dfs(int v){ // 点分治 queue<int> Q; // 记录flag数组为true的下标，用于清空 flag[0] = true; vis[v] = true; for(PII e : G[v]){ if(vis[e.first])continue; cnt = 0; dis[e.first] = e.second; getdis(e.first, v); for(int j = 1; j <= cnt; ++j) for(int k = 0; k < m; ++k) if(que[k] >= dd[j]) ans[k] |= flag[que[k] - dd[j]]; for(int j = 1; j <= cnt; ++j) if(dd[j] < V) flag[dd[j]] = true, Q.push(dd[j]); } while(!Q.empty())flag[Q.front()] = false, Q.pop(); for(PII e : G[v]){ if(vis[e.first])continue; masz = n; tot = siz[e.first]; dfsize(e.first, 0); dfsize(rt, 0); dfs(rt); } } int main(){ IOS; cin >> n >> m; for(int u, v, w, i = 1; i < n; ++i){ cin >> u >> v >> w; G[u].emplace_back(v, w); G[v].emplace_back(u, w); } for(int i = 0; i < m; ++i) cin >> que[i]; masz = n; tot = n; dfsize(1, 0); dfsize(rt, 0); dfs(rt); for(int i = 0; i < m; ++i) cout << (ans[i] ? "AYE" : "NAY") << endl; }树上启发式合并，其实是一个树版本的并查集。所以它的时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)。解决的问题是在 O ( n log n ) O(n \log n) O(nlogn)的总时间复杂度下，找u子树中，有多少个点具有某种性质。 思想是维护一些全局的变量（数组），当dfs到u的时候，这些变量代表的是u子树的信息。当向上传递的时候，只有重儿子才会向上传递，轻儿子要把做的改变恢复（或者说清空，有时候清空比逆操作快）。 heavy-light decomposition style模板 问题：求每个u子树下，颜色为c的点的数量。 该模板中，要先求出所有点的子树大小。dfs部分不需要修改，只需要修改add函数。
int cnt[maxn]; bool big[maxn]; void add(int v, int p, int x){ cnt[ col[v] ] += x; for(auto u: g[v]) if(u != p && !big[u]) add(u, v, x) } void dfs(int v, int p, bool keep){ int mx = -1, bigChild = -1; for(auto u : g[v]) if(u != p && sz[u] > mx) mx = sz[u], bigChild = u; for(auto u : g[v]) if(u != p && u != bigChild) dfs(u, v, 0); // run a dfs on small childs and clear them from cnt if(bigChild != -1) dfs(bigChild, v, 1), big[bigChild] = 1; // bigChild marked as big and not cleared from cnt add(v, p, 1); //now cnt[c] is the number of vertices in subtree of vertex v that has color c. You can answer the queries easily. if(bigChild != -1) big[bigChild] = 0; if(keep == 0) add(v, p, -1); }题意： 一颗有点权有根树，问u子树下数量最多的点权的和。 思想：每个点维护1、子树下所有点权的数量；2、子树下最大的点权数量；3、最多点权数量的点权和。
#include<bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //#define endl '\n' typedef long long LL; const int N = 1e5 + 5; int n, c[N], siz[N], cnt[N], big[N]; LL ans[N], sum = 0; int maxcnt = 0; vector<int> G[N]; void dfsize(int u, int fa){ siz[u] = 1; for(int v : G[u]){ if(v == fa)continue; dfsize(v, u); siz[u] += siz[v]; } } void add(int u, int fa, int x){ cnt[c[u]] += x; if(cnt[c[u]] == maxcnt){ sum += c[u]; } else if(cnt[c[u]] > maxcnt){ maxcnt = cnt[c[u]]; sum = c[u]; } for(int v : G[u]){ if(v != fa && !big[v]) add(v, u, x); } } void dfs(int u, int fa, bool keep){ int ms = 0, son = 0; for(int v : G[u]){ if(v == fa)continue; if(siz[v] > ms){ ms = siz[v]; son = v; } } for(int v : G[u]){ if(v == fa || v == son)continue; dfs(v, u, 0); } if(son)dfs(son, u, 1), big[son] = 1; add(u, fa, 1); ans[u] = sum; if(son)big[son] = 0; if(!keep){ add(u, fa, -1); maxcnt = 0; sum = 0; } } int main(){ IOS; cin >> n; for(int i = 1; i <= n; ++i){ cin >> c[i]; } for(int u, v, i = 1; i < n; ++i){ cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } dfsize(1, 0); dfs(1, 0, 1); for(int i = 1; i <= n; ++i){ if(i != n)cout << ans[i] << " "; else cout << ans[i] << endl; } }题意：一颗有根树，叶子结点具有权值，求每个子树下，叶子权重差的最小值。 思路：维护子树的叶子权重的一个map。插入时，查找前驱后继，更新最小权重差。 O ( n log 2 n ) O(n\log^2 n) O(nlog2n)
题意：给一个森林。每个节点有一个名字，查询v子树下第k层中，不同的名字的数量。 思路：维护每一层的不同名字的set。查询直接输出nset[dep[v]+k].size()。 O ( n log 2 n ) O(n\log^2 n) O(nlog2n)
n+1个节点选m+1个节点，让权值之和最大。选子节点要先选父节点。
#include<bits/stdc++.h> using namespace std; #define endl '\n' using ll = long long; using pii = pair<int,int>; const int maxn=1e5+3; const ll mod=1e9+7; vector<int> G[305]; int n,m,s[305]; int f[305][305]; void dfs(int x){ f[x][1] = s[x]; for(int v : G[x]){ dfs(v); for(int i=m;i>1;--i){ for(int j=i-1;j>0;--j) f[x][i] = max(f[x][i],f[x][j]+f[v][i-j]); } } } int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n>>m; for(int v,ts,i=1;i<=n;++i){ cin>>v>>s[i]; G[v].push_back(i); } m+=1; dfs(0); cout<<f[0][m]<<endl; }给一棵树，每个节点有一个字母，多次查询（v h），问v节点的子树中从深度为h（1号节点为跟）的所有节点中字母可不可以组成回文串。
每一层可以用异或前缀和来存储字母个数奇偶性，任务转化为找v节点下第一个该层节点和最后一个该层节点快速寻找的方式是记录进入子树in[v]和离开子树out[v]的DFS序，比in[v]大的第一个该层节点即为第一个节点，比out[v]小的第一个节点则为最后一个节点。 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair const int maxn = 5e5 + 5; using pii = pair<int, int>; int pow2[32]; int cnt = 0; char s[maxn]; vector<pii> H[maxn]; vector<int> G[maxn]; int in[maxn], out[maxn]; void dfs(int u, int dep){ in[u] = ++cnt; H[dep].pb(mp(cnt, H[dep].back().second ^ pow2[s[u] - 'a'])); for(int son : G[u]){ dfs(son, dep + 1); } out[u] = ++cnt; } int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n, q; for(int i=0;i<32;++i){ pow2[i] = 1 << i; } cin>>n>>q; for(int i=1;i<=n;++i){ H[i].resize(1); } for(int tf, i = 2; i <= n;++i){ cin>>tf; G[tf].pb(i); } cin>>(s+1); dfs(1, 1); int v, h, l, r; while(q--){ cin>>v>>h; l = lower_bound(H[h].begin(), H[h].end(), mp(in[v], -1)) - H[h].begin() - 1; r = lower_bound(H[h].begin(), H[h].end(), mp(out[v], -1)) - H[h].begin() - 1; v = H[h][l].second ^ H[h][r].second; // cout<<"*"<<l<<" "<<r<<endl; if(v - (v & -v))cout<<"No\n"; else cout<<"Yes\n"; } }题意：求合法的根（到所有点的路径上任意点权各不相同的根）的数量。 思路：若两点点权相同，则两点左右的点都一定是非法的。应该找到所有非法的点。
考虑一个点和它的某个子树的点有相同点权。如图， 1 1 1的 2 2 2子树有相同点权点 4 4 4，则子树 2 2 2以外的所有点都是非法的。考虑一个点和它的子树以外的点有相同点权。如图， 4 4 4和非自己子树的 1 1 1相同，则 4 4 4的整个子树非法。维护子树整体，和其他的部分之间的关系。DFS序是最好的方式。区间修改，采用差分数组。而判断子树内有无点相同，可以用实时统计的map。dfs前后统计，判断该权值的点数量变化。判断非子树是否存在相同点，则用全局的该权值点数减去子树下的点数判断。
#include<bits/stdc++.h> #define endl '\n' #define pb push_back #define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0); using namespace std; typedef long long LL; const int N = 2e5 + 5, mod = 1e9; int n, a[N], cnt, id[N], diff[N], siz[N]; vector<int> G[N]; map<int, int> now, all; void dfs(int u, int fa){ siz[u] = 1; id[u] = ++cnt; ++now[a[u]]; for(int v : G[u]){ if(v == fa)continue; int x = now[a[u]], y = now[a[v]]; dfs(v, u); siz[u] += siz[v]; if(x < now[a[u]]){ // v子树下有相同，删除 ++diff[1]; --diff[id[v]]; ++diff[id[v] + siz[v]]; } if(all[a[v]] - (now[a[v]] - y) > 0){ // v子树以外有相同，删除子树 ++diff[id[v]]; --diff[id[v] + siz[v]]; } } } int main(){ IOS; cin >> n; for(int i = 1; i <= n; ++i){ cin >> a[i]; ++all[a[i]]; } for(int x, y, i = 1; i < n; ++i){ cin >> x >> y; G[x].pb(y); G[y].pb(x); } dfs(1, 0); int ans = 0; for(int now = 0, i = 1; i <= n; ++i){ now += diff[i]; if(!now)++ans; } cout << ans << endl; }通过重轻链剖分，把树放在线段树上维护，可以同时修改/查询一段路径or一颗子树。
在(u,v)路径上查询，修改。在v子树上进行查询、修改。
#include<bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define endl '\n' #define fi first #define se second #define mp make_pair #define lson rt << 1, l, mid #define rson rt << 1|1, mid + 1, r typedef long long LL; typedef pair<LL, int> PLI; const int N = 1e5 + 5; int n, m; LL p; vector<int> G[N]; int dfsid = 0; int top[N], son[N], sz[N], dep[N], id[N], fa[N]; int w[N], wt[N]; int tr[N << 2], lazy[N << 2]; //---------------- segment tree -------------------------- void pushup(int rt){ tr[rt] = (tr[rt << 1] + tr[rt << 1 | 1]) % p; } void pushdown(int rt, int l, int r){ if(lazy[rt]){ int mid = l + r >> 1, ls = rt << 1, rs = rt << 1 | 1; lazy[ls] = (lazy[ls] + lazy[rt]) % p; lazy[rs] = (lazy[rs] + lazy[rt]) % p; tr[ls] = (tr[ls] + lazy[rt] * (mid - l + 1) % p) % p; tr[rs] = (tr[rs] + lazy[rt] * (r - mid) % p) % p; lazy[rt] = 0; } } void build(int rt, int l, int r){ if(l == r){ tr[rt] = wt[l]; lazy[rt] = 0; return; } int mid = l + r >> 1; build(lson); build(rson); pushup(rt); } LL query(int rt, int l, int r, int ql, int qr){ if(ql <= l && r <= qr){ return tr[rt]; } pushdown(rt, l, r); int mid = l + r >> 1; LL res = 0; if(ql <= mid) res += query(lson, ql, qr); if(mid < qr) res += query(rson, ql, qr); return res % p; } void update(int rt, int l, int r, int ul, int ur, int val){ if(ul <= l && r <= ur){ tr[rt] = (tr[rt] + val * (r - l + 1) % p) % p; lazy[rt] = (lazy[rt] + val) % p; return; } pushdown(rt, l, r); int mid = l + r >> 1; if(ul <= mid) update(lson, ul, ur, val); if(mid < ur) update(rson, ul, ur, val); pushup(rt); } //--------------------------------------------------------- LL qSon(int x){ // subtree query return query(1, 1, n, id[x], id[x] + sz[x] - 1); } LL qRange(int x, int y){ // path query LL ans = 0; while(top[x] != top[y]){ if(dep[top[x]] < dep[top[y]])swap(x, y); ans += query(1, 1, n, id[top[x]], id[x]); ans %= p; x = fa[top[x]]; } if(dep[x] < dep[y])swap(x, y); ans += query(1, 1, n, id[y], id[x]); return ans %= p; } void uSon(int x, int z){ // update value in subtree update(1, 1, n, id[x], id[x] + sz[x] - 1, z); } void uRange(int x, int y, int z){ // update node value on path while(top[x] != top[y]){ if(dep[top[x]] < dep[top[y]])swap(x, y); update(1, 1, n, id[top[x]], id[x], z); x = fa[top[x]]; } if(dep[x] < dep[y])swap(x, y); update(1, 1, n, id[y], id[x], z); } void dfs(int u, int p){ sz[u] = 1; fa[u] = p; dep[u] = dep[p] + 1; int msz = 0, node = 0; for(int v : G[u]){ if(v == p) continue; dfs(v, u); sz[u] += sz[v]; if(sz[v] > msz)msz = sz[v], node = v; } son[u] = node; // heavy son } void dfs2(int u, int topx){ id[u] = ++dfsid; // dfs ordering wt[dfsid] = w[u]; // map origin value to segment tree top[u] = topx; // top node on chain if(son[u])dfs2(son[u], topx); for(int v : G[u]) if(v != fa[u] && v != son[u]) dfs2(v, v); } int main(){ IOS; int root; cin >> n >> m >> root >> p; for(int i = 1; i <= n; ++i){ cin >> w[i]; } for(int u, v, i = 1; i < n; ++i){ cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } dfs(root, 0);//cout << "---" << endl; dfs2(root, root);//cout << "---" << endl; build(1, 1, n); int op, x, y, z; while(m--){ cin >> op >> x; if(op == 1){ cin >> y >> z; uRange(x, y, z); // add z on path from x to y }else if(op == 2){ cin >> y; cout << qRange(x, y) << endl; // query value on path from x to y }else if(op == 3){ cin >> z; uSon(x, z); // add z in subtree x }else{ cout << qSon(x) << endl; // query subtree x } } }题意：n个点的有根树上，有m个girl，第 i i i个girl的初始重量为 i i i。有两种操作。
在(u,v)路径上，找最轻的k个girl，并删除。把v子树上所有的女孩的体重增加k。思路：树链剖分模板题。搞一个vector数组girl[v]表示v点上的女孩列表。reverse之后，列表中的女孩数量单调递减。
找 k k k个最轻的女孩相当于分 k k k次找，只要考虑找最大即可。线段树维护<该段最轻体重，其所在的点>。找出之后，要把女孩pop掉，并重置线段树该点为下一个女孩的原始重量加曾经加过的重量。加过的重量可以通过刚刚pop掉的女孩的原始重量算出。 #include<bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define endl '\n' #define fi first #define se second #define mp make_pair #define lson rt << 1, l, mid #define rson rt << 1|1, mid + 1, r #define dj cout << "hello" << endl; typedef long long LL; typedef pair<LL, int> PLI; const int N = 1e5 + 5; const LL INF = 2e18; int n, m, q; vector<int> G[N], girl[N]; int dfsid = 0; int top[N], son[N], sz[N], dep[N], id[N], fa[N]; int wt[N]; LL lazy[N << 2]; PLI tr[N << 2]; //---------------- segment tree -------------------------- void pushup(int rt){ tr[rt] = min(tr[rt << 1], tr[rt << 1 | 1]); } void pushdown(int rt, int l, int r){ if(lazy[rt]){ int mid = l + r >> 1, ls = rt << 1, rs = rt << 1 | 1; lazy[ls] = lazy[ls] + lazy[rt]; lazy[rs] = lazy[rs] + lazy[rt]; tr[ls].first = tr[ls].first + lazy[rt]; tr[rs].first = tr[rs].first + lazy[rt]; lazy[rt] = 0; } } LL getGirl(int x, LL dv = 0){ if(girl[x].empty())return INF; else return girl[x].back() + dv; } void build(int rt, int l, int r){ if(l == r){ tr[rt] = make_pair(getGirl(wt[l]), wt[l]); lazy[rt] = 0; return; } int mid = l + r >> 1; build(lson); build(rson); pushup(rt); } PLI query(int rt, int l, int r, int ql, int qr){ //cout << rt << "===" << l << " " << r << endl; if(ql <= l && r <= qr){ return tr[rt]; } pushdown(rt, l, r); int mid = l + r >> 1; PLI res(INF, -1); if(ql <= mid) res = min(res, query(lson, ql, qr)); if(mid < qr) res = min(res, query(rson, ql, qr)); return res; } void update(int rt, int l, int r, int ul, int ur, int val){ if(ul <= l && r <= ur){ tr[rt].first = tr[rt].first + val; lazy[rt] = lazy[rt] + val; return; } pushdown(rt, l, r); int mid = l + r >> 1; if(ul <= mid) update(lson, ul, ur, val); if(mid < ur) update(rson, ul, ur, val); pushup(rt); } void set_element(int rt, int l, int r, int key, LL dv){ if(id[key] == r && id[key] == l){ tr[rt] = make_pair(getGirl(key, dv), key); lazy[rt] = 0; return; } pushdown(rt, l, r); int mid = l + r >> 1; if(id[key] <= mid) set_element(lson, key, dv); else set_element(rson, key, dv); pushup(rt); } //--------------------------------------------------------- PLI qRange(int x, int y){ // path query PLI ans(INF, -1); while(top[x] != top[y]){ if(dep[top[x]] < dep[top[y]])swap(x, y); ans = min(ans, query(1, 1, n, id[top[x]], id[x])); x = fa[top[x]]; } if(dep[x] < dep[y])swap(x, y); ans = min(ans, query(1, 1, n, id[y], id[x])); return ans; } void uSon(int x, int z){ // update value in subtree update(1, 1, n, id[x], id[x] + sz[x] - 1, z); } void dfs(int u, int p){ sz[u] = 1; fa[u] = p; dep[u] = dep[p] + 1; int msz = 0, node = 0; for(int v : G[u]){ if(v == p) continue; dfs(v, u); sz[u] += sz[v]; if(sz[v] > msz)msz = sz[v], node = v; } son[u] = node; // heavy son } void dfs2(int u, int topx){ id[u] = ++dfsid; // dfs ordering wt[dfsid] = u; // map origin value to segment tree top[u] = topx; // top node on chain if(son[u])dfs2(son[u], topx); for(int v : G[u]) if(v != fa[u] && v != son[u]) dfs2(v, v); } int main(){ IOS; cin >> n >> m >> q; for(int v, u, i = 1; i < n; ++i){ cin >> v >> u; G[v].push_back(u); G[u].push_back(v); } for(int ci, i = 1; i <= m; ++i){ cin >> ci; girl[ci].push_back(i); } for(int i = 1; i <= n; ++i) reverse(girl[i].begin(), girl[i].end()); dfs(1, 0); dfs2(1, 1); build(1, 1, n); while(q--){ int op, v, u, k; cin >> op >> v; if(op == 1){ cin >> u >> k; vector<LL> ans; PLI tmp; while(k--){ if((tmp = qRange(v, u)).first == INF)break; ans.push_back(girl[tmp.second].back()); LL dv = tmp.first - girl[tmp.second].back(); girl[tmp.second].pop_back(); set_element(1, 1, n, tmp.second, dv); } cout << ans.size(); for(LL i : ans) cout << " " << i; cout << endl; }else{ cin >> k; uSon(v, k); } } }题意：一棵有点权的树上，每次查询u和v之间路径上最大异或和。多次查询。 思路： 对于每个f[x][i]求出整段的线性基。那么查询只需要在倍增求lca过程中合并线性基就行了。
#include <bits/stdc++.h> #define endl '\n' using namespace std; using ll = long long; const int maxn = 2e4 + 5; struct JI{ ll a[62]; JI(){ memset(a, 0, sizeof(a)); } void add(ll x){ for(ll i = 60; i >= 0; --i){ if(x & (1ll<<i)){ if(!a[i]){ a[i] = x; return; }else x ^= a[i]; } } } ll jmax(ll base){ for(int i = 60; i >= 0; --i) base = max(base, base ^ a[i]); return base; } }; vector<int> G[maxn]; int dep[maxn], f[maxn][20]; ll a[maxn]; JI ji[maxn][20]; JI merge_ji(const JI &x, const JI &y){ JI res; for(int i = 60; i >= 0; --i){ if(x.a[i])res.add(x.a[i]); if(y.a[i])res.add(y.a[i]); } return res; } void dfs(int u, int fa, int d){ f[u][0] = fa; ji[u][0].add(a[u]); dep[u] = d; for(int son : G[u]){ if(son==fa)continue; dfs(son, u, d + 1); } } JI lca(int x, int y){ if(dep[x] < dep[y])swap(x, y); int t = dep[x] - dep[y]; JI res; for(int i=0;i<20;++i) if(t&(1<<i)){ res = merge_ji(res, ji[x][i]); x = f[x][i]; } if(x==y){ res.add(a[x]); return res; } for(int i=19;i>=0;--i){ if(f[x][i] != f[y][i]){ res = merge_ji(res, ji[x][i]); res = merge_ji(res, ji[y][i]); x = f[x][i]; y = f[y][i]; } } res.add(a[x]); res.add(a[y]); res.add(a[f[x][0]]); return res; } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n, q; cin >> n >> q; for(int i = 1; i <= n; ++i){ cin >> a[i]; } int x, y; for(int i=1;i<n;++i){ cin >> x >> y; G[x].push_back(y); G[y].push_back(x); } dfs(1, 0, 1); for(int i = 1; i < 20; ++i){ for(int j = 1; j <= n; ++j){ f[j][i] = f[f[j][i-1]][i-1]; ji[j][i] = merge_ji(ji[j][i-1], ji[f[j][i-1]][i-1]); } } while(q--){ cin >> x >> y; cout << lca(x, y).jmax(0) << endl; } }题意：给一棵有边权树，求有序三元组 ( i , j , k ) (i,j,k) (i,j,k)， i i i到 j j j， i i i到 k k k的路径上都有Lucy边。（Lucy边：边权每一位都是4或7） 思路：
只要求到每个点 i i i经过Lucy边能到达的点数 s i s_i si，则答案就是 ∑ 1 ≤ i ≤ n s i ⋅ ( s i − 1 ) \sum_{1\le i \le n}s_i\cdot (s_i - 1) ∑1≤i≤nsi⋅(si−1)。任意两个点的路径上没有Lucy边的话， s i = = s j s_i==s_j si==sj。所以，可以并查集把没有Lucy边相连的点合在一起，则 s i = n − s i z [ i ] s_i=n-siz[i] si=n−siz[i]
#include<bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //#define endl '\n' typedef long long LL; const int N = 1e5 + 5; int n, f[N], siz[N]; bool is47(int x){ while(x){ if(x % 10 != 7 && x % 10 != 4)return false; x /= 10; } return true; } int findroot(int x){ return f[x] == x ? x : (f[x] = findroot(f[x])); } bool merge(int x, int y){ x = findroot(x), y = findroot(y); if(x != y){ f[x] = y; siz[y] += siz[x]; siz[x] = 0; return true; } return false; } int main(){ IOS; cin >> n; for(int i = 1; i <= n; ++i){ f[i] = i; siz[i] = 1; } for(int u, v, w, i = 1; i < n; ++i){ cin >> u >> v >> w; if(!is47(w))merge(u, v); } LL ans = 0; for(int i = 1; i <= n; ++i){ if(f[i] != i)continue; ans += 1ll * siz[i] * (n - siz[i]) * (n - siz[i] - 1); } cout << ans << endl; }