题目
输入
样例输入
7 7
3 1
2 1
7 6
6 3
5 3
4 3
7 2 3
7 1 1
2 3 5
3 6 2
4 2 4
5 3 10
6 1 20
3
5
6
7
输出
样例输出
10
22
5
数据范围
剖解题目
给一棵树，在v点你可以花费一定代价w向上走1~k个节点，问从一些点出发走到根（1）点的最小花费。
思路
比赛时想到是dp。
设f[i]表示从i点走到根所需要的最小花费，那么很明显
很明显就是优化取树上一段区间的最小值嘛。
当时想打树链剖分的，后来听到说不用那么麻烦，打个倍增就好了，然后想想倍增确实短，虽然打的少，不过应该能打出来。
然后比赛时就没改出来。
后来课后改出来后，对比了一下比赛时的代码。
发现不同的只有一处。。。。。(╯‵□′)╯︵┻━┻。
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define down(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=1e5+5,M=20;
int f[maxn],mi[maxn][M],next[maxn*2],go[maxn*2],fre[maxn],deep[maxn],up[maxn][M];
int er[M],fir[maxn];
int n,m,q,num,nn;
struct cy{
int w,k,next;
}tic[maxn];
int read()
{
int x=0,sig=1;
char c;
for (c=getchar();c<'0' || c>'9';c=getchar()) if (c=='-') sig=-1;
for (;c>='0' && c<='9';c=getchar()) x=x*10+c-48;
return x*sig;
}
void add(int x,int y)
{
go[++num]=y;
next[num]=fre[x];
fre[x]=num;
}
void build(int x,int k,int w)
{
tic[++nn].k=k;
tic[nn].w=w;
tic[nn].next=fir[x];
fir[x]=nn;
}
void dfs(int x,int fa)
{
if (x!=1){
up[x][0]=fa;
for(int i=fir[x];i;i=tic[i].next){
int xx=fa,k=tic[i].k-1,minn=f[xx]（就是这）;
down(j,17,0)
if (k>=er[j]&&up[xx][j]){
minn=min(minn,mi[xx][j]);
k-=er[j];
xx=up[xx][j];
}
f[x]=min(minn+tic[i].w,f[x]);
}
up[x][0]=fa; mi[x][0]=min(f[x],f[fa]);
fo(i,1,17) up[x][i]=up[up[x][i-1]][i-1],mi[x][i]=min(mi[x][i-1],mi[up[x][i-1]][i-1]);
}
for(int i=fre[x];i;i=next[i]){
int u=go[i];
if(go[i]!=fa) dfs(u,x);
}
}
int main()
{
// freopen("T.in","r",stdin);
n=read(); m=read();
fo(i,1,n-1){
int x=read(),y=read();
add(x,y); add(y,x);
}
er[0]=1;
fo(i,1,17) er[i]=er[i-1]*2;
fo(i,1,m){
int x=read(),k=read(),w=read();
build(x,k,w);
}
memset(mi,127,sizeof(mi));
memset(f,127,sizeof(f));
f[1]=f[0]=mi[1][0]=0;
up[1][0]=1;
dfs(1,1);
q=read();
fo(i,1,q){
int now=read();
printf("%d\n",f[now]);
}
} 