2599: [IOI2011]Race Time Limit: 70 Sec Memory Limit: 128 MB 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
/* 点分治. */ #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #define MAXN 200001 using namespace std; int n,m,root,k,f[MAXN],total,dis[MAXN],dist[MAXN],t[MAXN],c[MAXN],ans[MAXN],tot,a[MAXN],sum,cut,head[MAXN],size[MAXN]; bool b[MAXN]; struct edge{int v,x,next;}e[MAXN*2]; struct data{int x,t;}s[MAXN]; 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-48,ch=getchar(); return x*f; } void add(int u,int v,int x) { e[++cut].v=v;e[cut].next=head[u];e[cut].x=x;head[u]=cut; } bool cmp(const data &x,const data &y) { return x.x<y.x; } void get_root(int u,int fa) { size[u]=1;f[u]=0; for(int i=head[u];i;i=e[i].next) { if(e[i].v==fa||b[e[i].v]) continue; get_root(e[i].v,u); size[u]+=size[e[i].v]; f[u]=max(f[u],size[e[i].v]); } f[u]=max(f[u],sum-size[u]); if(f[u]<f[root]) root=u; return ; } void get_dis(int u,int fa) { total++;s[++tot].x=dis[u],s[tot].t=dist[u]; for(int i=head[u];i;i=e[i].next) { if(e[i].v==fa||b[e[i].v]) continue; dis[e[i].v]=dis[u]+e[i].x; dist[e[i].v]=dist[u]+1; get_dis(e[i].v,u); } return ; } void erfen(int l,int r,int z) { int total=0; sort(s+1,s+tot+1,cmp);// 1 W. s[0].x=1e9; while(l<=r) { while(l<r&&s[l].x+s[r].x>k) r--; int j=r; while(l<j&&s[l].x+s[j].x==k) ans[s[l].t+s[j].t]+=z,j--; l++; } return ; } void Go(int u,int d,int t,int flag) { dis[u]=d;dist[u]=t;tot=0; get_dis(u,u); erfen(1,tot,flag); return ; } void slove(int u) { b[u]=true;Go(u,0,0,1); for(int i=head[u];i;i=e[i].next) { if(b[e[i].v]) continue; Go(e[i].v,e[i].x,1,-1); root=0;sum=size[e[i].v]; get_root(e[i].v,root); slove(root); } return ; } int main() { int x,y,z; n=read(),k=read(); for(int i=1;i<=n-1;i++) { x=read(),y=read(),z=read(); x++,y++; add(x,y,z),add(y,x,z); } f[0]=1e9;sum=n; get_root(1,root); slove(root); for(int i=1;i<=n;i++) if(ans[i]) {printf("%d",i);return 0;} printf("-1"); return 0; }