【bzoj 2599】Race点分治
ACチャネル:http://www.lydsy.com/JudgeOnline/problem.php?id=2599
【問題解】
黄先輩の問題解を直接呼び出します.
100 Wの配列tを開き、t[i]は重み値iの経路の最小辺数を表す
重心がいくつかのサブツリーに分かれていることを見つけた後、1本のサブツリーのすべての点からルートへの重み値とxを得て、ルートaの辺まで、t[k-x]+aで答えを更新して、すべて検索し終わった後
そしてt[x]をすべてaで更新する
これにより、点分治中の不法な状況が発生しないことを保証することができる.
1本の木のすべてのサブツリーを完成した後に更にすべてのサブツリーを遍歴してT配列を回復して、memsetを使うならば比較的に遅いはずです
【問題解】
黄先輩の問題解を直接呼び出します.
100 Wの配列tを開き、t[i]は重み値iの経路の最小辺数を表す
重心がいくつかのサブツリーに分かれていることを見つけた後、1本のサブツリーのすべての点からルートへの重み値とxを得て、ルートaの辺まで、t[k-x]+aで答えを更新して、すべて検索し終わった後
そしてt[x]をすべてaで更新する
これにより、点分治中の不法な状況が発生しないことを保証することができる.
1本の木のすべてのサブツリーを完成した後に更にすべてのサブツリーを遍歴してT配列を回復して、memsetを使うならば比較的に遅いはずです
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define FILE "read"
#define MAXN 200010
#define INF 1000000000
#define up(i,j,n) for(int i=j;i<=n;++i)
#define dn(i,j,n) for(int i=j;i>=n;--i)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
namespace INIT{
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
int x=0,f=1; char ch=getc();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getc();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getc();}
return x*f;
}
}using namespace INIT;
struct node{int y,next,v;}e[MAXN*2];
int n,m,len,root,sum,ans(INF),Link[MAXN],vis[MAXN],dis[MAXN],deep[MAXN],f[MAXN],size[MAXN],t[1000010];
void insert(int x,int y,int v){e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;}
void getroot(int x,int fa){
size[x]=1; f[x]=0;
for(int i=Link[x];i;i=e[i].next){
if(vis[e[i].y]||e[i].y==fa) continue;
getroot(e[i].y,x); size[x]+=size[e[i].y];
cmax(f[x],size[e[i].y]);
}
cmax(f[x],sum-size[x]);
if(f[x]