YZOJ P3924 [IOI2011]Race
时间限制：2000MS 内存限制：131072KB
难度：\(7.0\)
-
题目描述
给一棵树，每条边有权。
求一条简单路径，权值和等于 \(K\) ，且经过边的数量最小。
\(N \leq 200000, K \leq 1000000\) 。
-
输入格式
第一行 两个整数 \(n\)，\(k\) 。
第 \(2\)~\(n\) 行 每行三个整数，表示一条无向边的两端和权值（注意点的编号从 \(0\) 开始）。
-
输出格式
一个整数，表示最小边数量。
如果不存在这样的路径，输出 \(-1\) 。
-
样例输入
|
1 2 3 4 |
4 3 0 1 1 1 2 2 1 3 4 |
-
样例输出
|
1 |
2 |
Source: BZOJ 2599
因为本题 \(K\) 较小，所以可能会有其他做法。
记 \(ans_i\) 为满足条件（权值和为 \(K\)），并且经过边数为 \(i\) 的点对的个数。
正贡献就是 \(+1\) ，消去重复答案就是 \(-1\) 。
然后就是一个裸的点分治。
使用双指针时注意有 \(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 109 110 111 112 113 114 115 116 117 118 119 120 121 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <algorithm> #define _max(_a_,_b_) ((_a_)>(_b_)?(_a_):(_b_)) #ifdef ONLINE_JUDGE char __B[1<<15],*__S=__B,*__T=__B; #define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++) #endif inline int getnum() { register char c=0; while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } int gcnt,ghead[205050],gnext[2050505],gnode[2050505],gval[2050505]; inline void insertLine(register int s,register int t,const int&val) { gnext[++gcnt]=ghead[s],ghead[s]=gcnt,gnode[gcnt]=t,gval[gcnt]=val; gnext[++gcnt]=ghead[t],ghead[t]=gcnt,gnode[gcnt]=s,gval[gcnt]=val; } int K; int root,mxsroot,asize,size[205050]; bool vis[205050]; void DFS_GetRoot(register int o,register int f) { size[o]=1; register int mxs=0; for(register int j=ghead[o],t;j;j=gnext[j]) if((t=gnode[j])!=f && !vis[t]) { DFS_GetRoot(t,o); size[o]+=size[t]; mxs=_max(mxs,size[t]); } mxs=_max(mxs,asize-size[o]); if(!root || mxs<mxsroot) mxsroot=mxs,root=o; } int depth[205050],dist[205050],llst,lst[205050]; void DFS_GetDepth(register int o,register int f) { lst[++llst]=o; for(register int j=ghead[o],t;j;j=gnext[j]) if((t=gnode[j])!=f && !vis[t]) { depth[t]=depth[o]+gval[j],dist[t]=dist[o]+1; DFS_GetDepth(t,o); } } struct _comp { bool operator () (const int&a,const int&b) { return depth[a]<depth[b]; } }; int ans[205050]; inline void CalcAns(register int o,register int diff=0,register int delta=1) { depth[o]=diff,dist[o]=(delta<0); llst=0,DFS_GetDepth(o,0); std::sort(&lst[1],&lst[llst+1],_comp()); register int l=1,r=llst; while(l<r) { while(l<r && depth[lst[l]]+depth[lst[r]] > K) r--; for(register int j=r;depth[lst[l]]+depth[lst[j]]==K && j>l;j--) ans[dist[lst[l]]+dist[lst[j]]]+=delta; l++; } } void DFS(register int o) { CalcAns(o); vis[o]=true; for(register int j=ghead[o],t;j;j=gnext[j]) if(!vis[t=gnode[j]]) { CalcAns(t,gval[j],-1); asize=size[t],root=mxsroot=0,DFS_GetRoot(t,0); DFS(root); } } int main() { register int N=getnum(),K=getnum(); ::K=K; for(register int i=1;i<=N-1;i++) { register int a=getnum()+1,b=getnum()+1,v=getnum(); insertLine(a,b,v); } asize=N,root=mxsroot=0,DFS_GetRoot(1,0); DFS(root); for(register int i=1;i<=N;i++) if(ans[i]) { printf("%d\n",i); return 0; } printf("%d\n",-1); return 0; } |