「题目描述」

给定一个N(2<=N<=150000)个节点N－1边的树，每条边有一个长度L（1<=L<=1000000）。

现在定义：

• “路径(u,v)长度”表示顶点u到v之间的最短路径
• “u的第k远路径”表示从顶点u出发的第k长路径。

请编写一个程序，计算这棵树中每个顶点的的第k远路径的长度。

「输入格式」

输入第一行包含一个整数T（T<=50），表示测试数据的组数。

在每一组测试数据中，第一行为两个整数N和K(1<=K<=20且K<=N-1)。接下来的N-1行，每行包含三个整数u,v,L（0<=u,v<=N-1）,表示顶点u到v有一条边长度为L。

「输出格式」

对于每组数据，输出一行，为N个整数（之间用一个空格隔开），其中第i(i=0,1,2,…,N-1)个整数表示顶点i的答案。

「样例输入」

2

4 1

0 1 4

1 2 5

2 3 9

3 2

0 1 12

0 2 19

「样例输出」

18 14 9 18

12 12 19

题解

树形dp。。。f[x]和g[x]分别表示从x出发，终点在/不在x的子树中的1-K远距离

转移的时候通过归并每次为K，还要搞类似前缀和后缀和的好麻烦。。

复杂度为TNK。。。

C++

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define inf 1000000000 #define ll long long #define N 150005 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n,K,cnt,tot; int last[N],st[N],val[N]; struct edge{int to,next,v;}e[N*2]; ll t1[N][25],t2[N][25],ans[N][25],f[N][25],g[N][25],t[25]; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=last[u];e[cnt].v=w;last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];e[cnt].v=w;last[v]=cnt; } void add(bool flag,ll *a,ll *b,ll *c,int w) { int t1=1,t2=1,cnt=0; while(cnt<K) { if(a[t1]>b[t2]+w||t2==-1)t[++cnt]=a[t1],t1++; else { if(b[t2]||flag)t[++cnt]=b[t2]+w; if(b[t2]==0)t2=-1; else t2++; } } for(int i=1;i<=K;i++)c[i]=t[i]; } void dfs(int x,int fa) { for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) { dfs(e[i].to,x); add(1,f[x],f[e[i].to],f[x],e[i].v); } } void solve(int x,int fa) { tot=0; for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) { st[++tot]=e[i].to; val[tot]=e[i].v; } for(int i=1;i<=tot;i++) { add(1,t1[i-1],f[st[i]],t1[i],val[i]); add(1,t2[i-1],f[st[tot-i+1]],t2[i],val[tot-i+1]); } for(int i=1;i<=tot;i++) { add(1,g[st[i]],g[x],g[st[i]],val[i]); add(0,g[st[i]],t1[i-1],g[st[i]],val[i]); add(0,g[st[i]],t2[tot-i],g[st[i]],val[i]); } for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) solve(e[i].to,x); } int main() { // freopen("kth.in","r",stdin); // freopen("kth.out","w",stdout); T=read(); while(T--) { cnt=0; memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); memset(last,0,sizeof(last)); n=read();K=read(); for(int i=1;i<n;i++) { int u=read(),v=read(),w=read(); u++;v++; insert(u,v,w); } dfs(1,0); solve(1,0); for(int i=1;i<=n;i++) { add(0,f[i],g[i],ans[i],0); printf("%I64d ",ans[i][K]); } puts(""); } return 0; }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define inf 1000000000 #define ll long long #define N 150005 using namespace std; int read() {     int x=0,f=1;char ch=getchar();     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}     return x*f; } int T,n,K,cnt,tot; int last[N],st[N],val[N]; struct edge{int to,next,v;}e[N*2]; ll t1[N][25],t2[N][25],ans[N][25],f[N][25],g[N][25],t[25]; void insert(int u,int v,int w) {     e[++cnt].to=v;e[cnt].next=last[u];e[cnt].v=w;last[u]=cnt;     e[++cnt].to=u;e[cnt].next=last[v];e[cnt].v=w;last[v]=cnt; } void add(bool flag,ll *a,ll *b,ll *c,int w) {     int t1=1,t2=1,cnt=0;     while(cnt<K)     { if(a[t1]>b[t2]+w||t2==-1)t[++cnt]=a[t1],t1++; else { if(b[t2]||flag)t[++cnt]=b[t2]+w; if(b[t2]==0)t2=-1; else t2++; }     }     for(int i=1;i<=K;i++)c[i]=t[i]; } void dfs(int x,int fa) {     for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) { dfs(e[i].to,x); add(1,f[x],f[e[i].to],f[x],e[i].v); } } void solve(int x,int fa) {     tot=0;     for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) { st[++tot]=e[i].to; val[tot]=e[i].v; }     for(int i=1;i<=tot;i++)     { add(1,t1[i-1],f[st[i]],t1[i],val[i]); add(1,t2[i-1],f[st[tot-i+1]],t2[i],val[tot-i+1]);     }     for(int i=1;i<=tot;i++)     { add(1,g[st[i]],g[x],g[st[i]],val[i]); add(0,g[st[i]],t1[i-1],g[st[i]],val[i]); add(0,g[st[i]],t2[tot-i],g[st[i]],val[i]);     }     for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) solve(e[i].to,x); } int main() {     // freopen("kth.in","r",stdin);     // freopen("kth.out","w",stdout);     T=read();     while(T--)     { cnt=0; memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); memset(last,0,sizeof(last)); n=read();K=read(); for(int i=1;i<n;i++) { int u=read(),v=read(),w=read(); u++;v++; insert(u,v,w); } dfs(1,0); solve(1,0);         for(int i=1;i<=n;i++) { add(0,f[i],g[i],ans[i],0); printf("%I64d ",ans[i][K]); } puts("");     }     return 0; }