差点就弃了,正好3小时,似乎变强了一点~
提示我遇到的细节问题:
求重心时,最大删除后子树大小的初值要设为INF
求重心时,当你用totSize-myMaxPart
更新最大删除后子树大小时,要防止整数溢出
计算答案时,不需要枚举两个点,只需要在递归时仅用之前的桶更新答案就行了
计算答案时,为了避免同一子树内互相更新,要在整棵子树更新完之后再将该子树中各个节点的值插入桶中
计算答案时,所有节点、任何时刻都可以和根节点一起更新答案,但不能让根节点自更新(如果你的实现跟我一样奇怪的话,有可能会出现这种情况;打卡的代码已经改了黑历史消除)
以下为巨水数据生成器
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
const int M = 4;
const int Z = 10;
typedef long long LL;
inline int rol ( int n ){
return (LL)rand()*rand()%n;
}
int main (){
srand ( (unsigned)time(0) );
freopen ( "data.in", "w", stdout );
int n = N; printf ( "%d %d\n", n, rol (45) );
for ( int i = 2; i <= n; ++i ){
int fa = rol (i-1)+1;
printf ( "%d %d %d\n", i-1, fa-1, rol (Z) );
}
return 0;
}
以下为AC代码
#include<bits/stdc++.h>
using namespace std;
namespace OI{
#define I inline
#define B break
typedef long long LL;
typedef long double LD;
typedef double D;
const int INF = 0x3f3f3f3f;
const int RINF = 0x7fffffff;
inline bool rd ( int &k ){
char c = getchar ();
bool neg = false;
while ( c != EOF && c != '-' && ( c < '0' || c > '9' ) )
c = getchar ();
if ( c == EOF ) return false;
if ( c == '-' ){
neg = true;
k = 0;
}else
k = c - '0';
c = getchar ();
while ( c >= '0' && c <= '9' ){
k = ( k << 1 ) + ( k << 3 ) + c - '0'; c = getchar ();
}
if ( neg ) k = -k;
return true;
}
inline bool lrd ( long long &k ){
char c = getchar ();
bool neg = false;
while ( c != EOF && c != '-' && ( c < '0' || c > '9' ) )
c = getchar ();
if ( c == EOF ) return false;
if ( c == '-' ){
neg = true;
k = 0;
}else
k = c - '0';
c = getchar ();
while ( c >= '0' && c <= '9' ){
k = ( k << 1 ) + ( k << 3 ) + c - '0'; c = getchar ();
}
if ( neg ) k = -k;
return true;
}
inline void freo (){
freopen ( "data.in", "r", stdin );
freopen ( "data.out", "w", stdout );
}
const int N = 200002;
const int M = 400002;
const int K = 1000002;
int toRoot [N], vis [N], size [N], vTot, eTot=1, dir [M], next [M], head [N], trueValue, erase [N];
int ans = RINF, req, val [M], bucket [K], version [K], versionNow, subTree [N], top, depth [N];
I void newEdge ( int u, int v, int k ){
int i = ++eTot;
dir [i] = v;
next [i] = head [u];
head [u] = i;
val [i] = k;
}
I void dfs1 ( int now, int &maxSize, int ¢erG, int totSize ){
vis [now] = trueValue;
size [now] = 1;
int myMaxSize = -INF;
for ( int i = head [now]; i; i = next [i] ){
int to = dir [i];
if ( erase [to] ) continue;
if ( vis [to] == trueValue ) continue;
dfs1 ( to, maxSize, centerG, totSize );
size [now] += size [to];
myMaxSize = max ( myMaxSize, size [to] );
}
myMaxSize = max ( myMaxSize, totSize - myMaxSize );
if ( myMaxSize < maxSize ){
maxSize = myMaxSize;
centerG = now;
}
}
I void dfs2 ( int now ){
if ( depth [now] && toRoot [now] <= req ){
if ( version [ req-toRoot[now] ] == versionNow ){
ans = min ( ans, depth [now] + bucket [ req-toRoot[now] ] );
}
}
subTree [++top] = now;
vis [now] = trueValue;
for ( int i = head [now]; i; i = next [i] ){
int to = dir [i];
if ( vis [to] == trueValue ) continue;
if ( erase [to] ) continue;
depth [to] = depth [now] + 1;
toRoot [to] = toRoot [now] + val [i];
dfs2 ( to );
}
}
I int searchRoot ( int any, int totSize ){
trueValue ++;
int root = 0, useless = RINF;
dfs1 ( any, useless, root, totSize );
return root;
}
I void calc ( int root ){
trueValue ++;
versionNow ++;
toRoot [root] = 0;
vis [root] = trueValue;
version [0] = versionNow;
bucket [0] = 0;
for ( int i = head [root]; i; i = next [i] ){
int to = dir [i];
if ( erase [to] ) continue;
top = 0;
toRoot [to] = val [i];
depth [to] = 1;
dfs2 ( to );
for ( int j = 1; j <= top; ++j ){
if ( toRoot [ subTree [j] ] <= req ){
if ( version [ toRoot [ subTree [j] ] ] == versionNow ){
bucket [ toRoot [ subTree [j] ] ] = min ( bucket [ toRoot [ subTree [j] ] ], depth [ subTree [j] ] );
}else{
version [ toRoot [ subTree [j] ] ] = versionNow;
bucket [ toRoot [ subTree [j] ] ] = depth [ subTree [j] ];
}
}
}
}
}
I void solve ( int any, int totSize ){
int root = searchRoot ( any, totSize );
calc ( root );
erase [root] = 1;
for ( int i = head [root]; i; i = next [i] ){
int to = dir [i];
if ( erase [to] ) continue;
solve ( to, size [to] );
}
}
void Main (){
// freo ();
rd ( vTot ); rd ( req );
for ( int i = 1; i < vTot; ++i ){
int u, v, k; rd ( u ); rd ( v ); rd ( k );
newEdge ( u, v, k ); newEdge ( v, u, k );
}
solve ( 1, vTot );
if ( ans == RINF ) puts ("-1");
else printf ( "%d", ans );
}
}
int main (){
OI :: Main ();
return 0;
}
有时间再写