首先，有一个推论，如果我们要保证能到达首都，那么朋友们的起点一定有车票，不然寸步难行啊！
所以，我们不用管那些没有车票的点了，直接考虑有车票的点。只有他们才可能作为朋友们的起点。
考虑DP。设 $f_u = min(f_v) + cost_u $. 其中，v 为 u 的祖先，$cost_u$即为u这个点的车票价额，其车票也必须保证可以从$u$到$v$（直接用深度算）。
不难想到，我们的DP必须要从上往下更新，因此要对车票进行排序。同时，我们需要找到其祖先的最小值,即$min(f_v)$,如果暴力枚举，肯定会T掉一部分。
考虑用数据结构来维护区间最小值。
于是，树剖+线段树横空出世：
用树剖获取每个点的$dfn$, 将车票按照$dfn$排序，然后建立关于$dp$数组的线段树，按照$dfn$维护区间最小值，同时快速查询。
于是，
此题AC。
#include <bits/stdc++.h> using namespace std; #define N 100001 #define ll long long /* dp[i] = min(dp[祖先] + cost[j]) cost 的车票应满足条件 */ inline int read(){ int x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); } return x * s; } struct node{ int v, next; } t[N << 1]; int f[N]; int n, m; ll dp[N]; int bian = 0; inline void add(int u, int v){ t[++bian] = (node){v, f[u]}, f[u] = bian; return ; } struct piao{ int x, k, cost; inline void insert(){ x = read(), k = read(), cost = read(); return ; } } g[N]; /*--------树剖begin--------*/ int top[N], fa[N], son[N], siz[N], deth[N]; int dfn[N], rev[N], id = 0; #define v t[i].v void dfs1(int now, int father){ fa[now] = father; siz[now] = 1; deth[now] = deth[father] + 1; for(int i = f[now]; i; i = t[i].next){ if(v != father){ dfs1(v, now); siz[now] += siz[v]; if(siz[v] > siz[son[now]]) son[now] = v; } } return ; } void dfs2(int now, int tp){ top[now] = tp; dfn[now] = ++id; rev[id] = now; if(!son[now]) return ; dfs2(son[now], tp); for(int i = f[now]; i; i = t[i].next){ if(v != fa[now] && v != son[now]) dfs2(v, v); } return ; } #undef v /*------end-------*/ /*------- segment tree ------*/ struct tree{ // 按照 dfn的顺序维护 dp 最小值 ll minn; } e[N << 2]; inline void pushup(int o){ e[o].minn = min(e[o << 1].minn, e[o << 1 | 1].minn); return ; } void build(int o, int l, int r){ if(l == r){ e[o].minn = (ll)1e18; return ; } int mid = l + r >> 1; build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r); pushup(o); return ; } void update(int o, int l, int r, int x, ll k){ if(l > x || r < x) return ; if(l == r && l == x){ e[o].minn = min(e[o].minn, (ll)k); return ; } int mid = l + r >> 1; update(o << 1, l, mid, x, k); update(o << 1 | 1, mid + 1, r, x, k); pushup(o); return ; } ll query(int o, int l, int r, int in, int end){ if(l > end || r < in){ return (ll)1e18; } if(l >= in && r <= end){ return e[o].minn; } int mid = l + r >> 1; return min(query(o << 1, l, mid, in, end), query(o << 1 | 1, mid + 1, r, in, end)); } ll ask_min(int x, int len){ ll now = x, temp = (ll)1e18; while(deth[x] - deth[top[now]] <= len && now){ // 注意排除根 temp = min(temp, query(1, 1, n, dfn[top[now]], dfn[now])); // 查找整条链上最小值 now = fa[top[now]]; } if(now == 1 || deth[x] - deth[now] > len) return temp; /*注意重链等特殊情况*/ ll l = dfn[top[now]], r = dfn[now], pos = r; ll mid = l + r >> 1; while(l <= r){ // 二分找该链上可到达位置 int mid = l + r >> 1; if(deth[x] - deth[rev[mid]] <= len) pos = mid, r = mid - 1; else l = mid + 1; } temp = min(temp, query(1, 1, n, pos, dfn[now])); return temp; } bool cmp(piao a, piao b){ // 按照 dfn 排序 return dfn[a.x] < dfn[b.x]; } int main(){ // freopen("hh.txt", "r", stdin); n = read(), m = read(); for(int i = 1; i < n; i++){ int x = read(), y = read(); add(x, y); add(y, x); // 加成多向边方便跑图 } dfs1(1, 0); //fa[1]必须设为0，防止影响到第二层的儿子 dfs2(1, 1); for(int i = 1;i <= m; i++) g[i].insert(); sort(g + 1, g + m + 1, cmp); // 按照 dfn 排序, 自上而下更新 dp memset(dp,37,sizeof(dp)); dp[1] = 0; build(1, 1, n); update(1, 1, n, 1, 0); for(int i = 1;i <= m; i++){ int x = g[i].x, k = g[i].k, cost = g[i].cost; if(x == 1) continue; // 排除根 ll temp = ask_min(x, k) + cost; if(temp < dp[x]){ dp[x] = min(dp[x], temp); // 起点必定有车票 update(1, 1, n, dfn[x], dp[x]); } } int Q = read(); while(Q--){ int x = read(); printf("%lld ", dp[x]); } return 0; }
update:
上面讲的实在是太麻烦了，或者说不好理解。考虑换个方法DP。
为何不用DP的好兄弟，记忆化搜索呢？
从题目中可以看出，每个朋友只会从当前点向上走，也就是只会前往每个点的父亲。那么记忆化搜搜的时间复杂度就会非常小啦！
贴一波代码：
#include <bits/stdc++.h> using namespace std; #define N 100010 const int inf = (int)9e9; inline int read(){ int x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); } return x * s; } int fa[N]; int n, m; int dp[N]; struct piao{ int u, k, w; } t[N]; vector <piao> T[N]; int dfs(int now){ if(now == 1) return 0; if(dp[now] != -1) return dp[now]; dp[now] = inf; for(int i = 0; i < T[now].size(); i++){ piao p = T[now][i]; int x = fa[now], limit = p.k, cnt = 1; while(x >= 1 && cnt <= limit){ dp[now] = min(dp[now], dfs(x) + p.w); x = fa[x]; cnt++; } } return dp[now]; } int main(){ n = read(), m = read(); for(int i = 1;i < n; i++){ int x = read(), y = read(); fa[x] = y; } memset(dp, -1, sizeof(dp)); for(int i = 1;i <= m; i++){ t[i].u = read(), t[i].k = read(), t[i].w = read(); T[t[i].u].push_back(t[i]); } int q = read(); while(q--){ int u = read(); printf("%d ", dfs(u)); } return 0; }