2599: [IOI2011]Race
Time Limit: 70 Sec Memory Limit: 128 MBSubmit: 4559 Solved: 1343[][][]Description
给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000
Input
第一行 两个整数 n, k
第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始)Output
一个整数 表示最小边数量 如果不存在这样的路径 输出-1
Sample Input
4 3 0 1 1 1 2 2 1 3 4
Sample Output
2
HINT
2018.1.3新加数据一组，未重测
分析：复习了一下点分治. 这道题在点分治模板的基础上改改就好了. dfs到一个点添加重心到它的距离和经过的边数，最后两个指针扫一下就好了.
#include#include #include #include #include using namespace std;const int maxn = 300010;int n,k,head[maxn],to[maxn * 2],nextt[maxn * 2],w[maxn * 2],tot = 1,d[maxn],num[maxn];int sizee[maxn],f[maxn],sum,root,vis[maxn],ans[1000010],anss = -1,top;struct node{ int p1,p2;}e[maxn];void add(int x,int y,int z){ w[tot] = z; to[tot] = y; nextt[tot] = head[x]; head[x] = tot++;}void findroot(int u,int fa){ sizee[u] = 1; f[u] = 0; for (int i = head[u]; i; i = nextt[i]) { int v = to[i]; if (vis[v] || v == fa) continue; findroot(v,u); sizee[u] += sizee[v]; f[u] = max(f[u],sizee[v]); } f[u] = max(f[u],sum - sizee[u]); if (f[u] < f[root]) root = u;}void dfs1(int u,int d1,int d2,int fa){ d[u] = d1; num[u] = d2; for (int i = head[u];i;i = nextt[i]) { int v = to[i]; if (vis[v] || v == fa) continue; dfs1(v,d1 + w[i],d2 + 1,u); }}void dfs2(int u,int fa){ e[++top].p1 = d[u]; e[top].p2 = num[u]; for (int i = head[u];i;i = nextt[i]) { int v = to[i]; if (vis[v] || v == fa) continue; dfs2(v,u); }}bool cmp(node a,node b){ if (a.p1 == b.p1) return a.p2 < b.p2; return a.p1 < b.p1;}void calc1(int u,int W){ top = 0; dfs2(u,0); sort(e + 1,e + 1 + top,cmp); int l = 1,r = top; while (l <= r) { while (l < r && e[l].p1 + e[r].p1 > k) r--; for (int kk = r; e[l].p1 + e[kk].p1 == k; kk--) //这里不是直接移动r. ans[e[kk].p2 + e[l].p2]++; l++; }}void calc2(int u,int W){ top = 0; dfs2(u,0); sort(e + 1,e + 1 + top,cmp); int l = 1,r = top; while (l <= r) { while (l < r && e[l].p1 + e[r].p1 > k) r--; for (int kk = r; e[l].p1 + e[kk].p1 == k; kk--) ans[e[kk].p2 + e[l].p2]--; l++; }}void solve(int u){ vis[u] = 1; dfs1(u,0,0,0); calc1(u,0); for (int i = head[u]; i; i = nextt[i]) { int v = to[i]; if (vis[v]) continue; calc2(v,w[i]); f[0] = sum = sizee[v]; findroot(v,root = 0); solve(root); }}int main(){ scanf("%d%d",&n,&k); for (int i = 1; i < n; i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); x++; y++; add(x,y,z); add(y,x,z); } f[0] = sum = n; findroot(1,0); solve(root); for (int i = 1; i <= n; i++) if (ans[i]) { anss = i; break; } printf("%d\n",anss); return 0;}