BZOJ2599 [IOI2011] [Race] 点分治

题意：给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小

solution：点分治

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 7;
const int Inf = 2000000000;
struct Edge{int v , w;Edge ( int v = 0 , int w = 0 ) : v(v) , w(w) {}
};
vector <Edge> edges;
vector <int> G[maxn*2];void addeage ( int u , int v , int w ){edges.push_back ( Edge ( v , w ) );int tot = edges.size();G[u].push_back ( tot - 1 );
}struct P{int d, p;
}a[maxn];int root , mxrt , sum , cnt , n , K;
int vis[maxn] , son[maxn];
int dep[maxn], dis[maxn];
int ans[maxn];void getroot( int u , int fa ){son[u] = 1;int mx = 0;for ( int i = 0 ; i < G[u].size() ; ++ i ){Edge e = edges[ G[u][i] ];if ( vis[e.v] != 0 || e.v == fa ) continue;getroot ( e.v , u );son[u] += son[e.v];mx = max ( mx , son[e.v] );}mx = max ( mx , sum - son[u] );if ( mx < mxrt ){root = u;mxrt = mx;}
}void getdis ( int u , int fa ){a[++cnt].d = dis[u] , a[cnt].p = dep[u];for ( int i = 0 ; i < G[u].size() ; ++ i ){Edge e = edges[G[u][i]];if ( e.v == fa || vis[e.v] ) continue;dep[e.v] = dep[u] + 1;dis[e.v] = dis[u] + e.w;getdis( e.v , u );  }   
}int cmp ( P x , P y ){return x.d < y.d;
}
void cal ( int u , int ndis , int ndep , int delta ){dis[u] = ndis , dep[u] = ndep , cnt = 0;getdis ( u , -1 );sort ( a + 1 , a + 1 + cnt , cmp );int l = 1 , r = cnt ;while ( l <= r ){while ( l<r && a[l].d + a[r].d > K ) -- r;int i = r;while ( a[l].d + a[i].d == K ){
// printf ( "find = %d %d %d %d\n" , a[l].d , a[i].d , a[l].p , a[i].p );ans[ a[l].p + a[i].p ] += delta;-- i;}++ l;}
}void work ( int x ){
// printf ( "root = %d\n" , x );vis[x] = 1;cal ( x , 0 , 0 , 1 );for ( int i = 0 ; i < G[x].size() ; ++ i ){Edge e = edges[G[x][i]];if ( vis[e.v] ) continue;cal ( e.v , e.w , 1 , -1 );root = 0;mxrt = Inf;sum = son[e.v];getroot( e.v , -1 );work ( root );}
}inline int readin(){int x = 0 , f = 1; char ch = getchar();while ( !isdigit(ch) ) {if ( ch == '-' ) f = -1;ch = getchar();}while ( isdigit(ch) ){x = x * 10 + ch - '0' ;ch = getchar();}return x*f;
}
int main(){
// freopen( "debug.in" , "r" , stdin );
// scanf ( "%d%d" , &n , &K );n = readin(), K = readin();
// memset( vis , 0 , sizeof(vis) );for ( int i = 1 ; i < n ; ++ i ){   int x , y , z;x = readin(), y = readin(), z = readin();
// scanf ( "%d%d%d" , &x , &y , &z );++ x , ++ y ;// printf ( "%d %d\n" , x , y );addeage ( x , y , z );addeage ( y , x , z );}
/* for ( int i = 1 ; i <= n ; ++ i ){printf ( "%d : ", i );for ( int j = 0 ; j < G[i].size() ; ++ j )printf ( " %d" , edges[G[i][j]].v );puts ( "" );} */  mxrt = Inf;sum = n;root = 0;getroot ( 1 , -1 );
// printf ( "root is %d \n" , root );work ( root );for ( int i = 1 ; i <= n ; i++ ) if ( ans[i] != 0 ){printf ( "%d" , i );return 0;}printf ( "-1" );return 0;
}