Link
感觉很有意思,非常想A掉这道题,但是找了好久都没有任何的题解或者AC代码。无奈看到过掉这道题的一位KUT小哥哥CF在线,于是讨教了一发,朝鲜小哥哥马上就回给我了AC代码!心里有点小激动
KUT小哥哥的function对象用的实在6…感觉这样写特别紧凑易读!
Solution
任何一个边数为c边权和为w的路径,在x点的值就是cx+w。
问题可以转化为一堆直线,求x点处最高的直线的纵坐标。
半平面交可以转化为凸包,因此维护一个全局凸包就行了。
点分治,对于分出来的子树的凸包,需要求出从不同子树选出两点加和产生新点集的凸包。
为了保证复杂度,KUT小哥哥用了类似线段树一样的分治思想。
这是这道题的精华部分,然而我现在还是不懂为什么KUT小哥哥AddHull
这么做是对的。先A了过几天再看看吧。
Code
const int XN=2e5+11;
struct Point {
long long x,y;
long long operator ()(int a) {
return x*a+y;
}
friend Point operator +(Point const &a,Point const &b) {
return Point{a.x+b.x,a.y+b.y};
}
friend Point operator -(Point const &a,Point const &b) {
return Point{a.x-b.x,a.y-b.y};
}
friend long long Outer(Point const &a,Point const &b) {
return a.x*b.y-a.y*b.x;
}
friend bool operator <(Point const &a,Point const &b) {
return a.x<b.x || (a.x==b.x && a.y<b.y);
}
};
std::vector<Point> ConvexHull(std::vector<Point> a) {
if(!std::is_sorted(a.begin(),a.end()))
std::sort(a.begin(),a.end());
std::vector<Point> hull;
for(Point p : a) {
while(hull.size()>1 && Outer(hull.back()-hull[hull.size()-2],p-hull.back())>=0)
hull.pop_back();
hull.push_back(p);
}
return hull;
}
std::vector<Point> MergeHull(std::vector<Point> const &a,std::vector<Point> const &b) {
std::vector<Point> c(a.size()+b.size());
std::merge(a.begin(),a.end(),b.begin(),b.end(),c.begin());
return ConvexHull(c);
}
std::vector<Point> AddHull(std::vector<Point> const &v1,std::vector<Point> const &v2) {
std::vector<Point> hull;
for(size_t p1=0,p2=0;p1<v1.size() && p2<v2.size();) {
hull.push_back(v1[p1]+v2[p2]);
if(p1+1<v1.size() && p2+1<v2.size()) {
if(Outer(v1[p1+1]-v1[p1],v2[p2+1]-v2[p2])<0)
++p1;
else
++p2;
} else if(p1+1<v1.size())
++p1;
else
++p2;
}
return hull;
}
struct Edge {
int to,v;
Edge *pre;
void *operator new(size_t flag) {
static Edge *pool=(Edge*)malloc(XN*2*sizeof(Edge)),*mem;
return flag?mem++:mem=pool;
}
}*G[XN];
void AddEdge(int x,int y,int v) {
G[x]=new Edge{y,v,G[x]};
G[y]=new Edge{x,v,G[y]};
}
long long mxw[XN];
bool ud[XN];
void DC(int pos=1) {
static int size[XN];
std::function<int(int)> Centroid=[&](int pos) {
std::function<void(int,int)> GetSize=[&](int pos,int fa) {
size[pos]=1;
for(Edge *e=G[pos];e;e=e->pre)
if(fa!=e->to && !ud[e->to]) {
GetSize(e->to,pos);
size[pos]+=size[e->to];
}
};
GetSize(pos,0);
int tot=size[pos];
bool found;
do {
found=0;
for(Edge *e=G[pos];e;e=e->pre)
if(!ud[e->to] && size[e->to]<size[pos] && size[e->to]*2>=tot) {
pos=e->to;
found=1;
break;
}
} while(found);
return pos;
};
static std::vector<Point> v[XN];
ud[pos=Centroid(pos)]=1;
std::vector<std::vector<Point>> all;
for(Edge *e=G[pos];e;e=e->pre)
if(!ud[e->to]) {
v[e->to].clear();
std::function<void(int,int,std::vector<Point>&,int,long long)> DFS=
[&](int pos,int fa,std::vector<Point> &v,int dep,long long length) {
Enlarge(mxw[dep],length);
v.push_back({dep,length});
for(Edge *e=G[pos];e;e=e->pre)
if(e->to!=fa && !ud[e->to])
DFS(e->to,pos,v,dep+1,length+e->v);
};
DFS(e->to,pos,v[e->to],1,e->v);
all.push_back(ConvexHull(v[e->to]));
}
std::function<void(int,int,int)> Solve=[&](int pos,int L,int R) {
static std::vector<Point> T[XN*4];
if(L==R)
T[pos]=all[L];
else {
int M=(L+R)/2;
Solve(pos<<1,L,M);Solve(pos<<1|1,M+1,R);
T[pos]=MergeHull(T[pos<<1],T[pos<<1|1]);
std::vector<Point> sum=AddHull(T[pos<<1],T[pos<<1|1]);
for(auto p : sum)
Enlarge(mxw[p.x],p.y);
}
};
if(all.size())
Solve(1,0,all.size()-1);
for(Edge *e=G[pos];e;e=e->pre)
if(!ud[e->to])
DC(Centroid(e->to));
}
void Work() {
int n,m;
fin>>n>>m;
Edge::operator new(0);
for(int i=1;i<=n;++i) {
G[i]=0;
mxw[i]=-1;
ud[i]=0;
}
for(int i=1;i<=n-1;++i) {
int x,y,v;fin>>x>>y>>v;
AddEdge(x,y,v);
}
DC();
std::vector<Point> poly;
for(int i=1;i<=n-1;++i)
if(mxw[i]>=0)
poly.push_back({i,mxw[i]});
poly=ConvexHull(poly);
for(int q=1;q<=m;++q) {
int x;fin>>x;
int L=0,R=poly.size()-1;
while(R-L>2) {
int M1=(L*2+R)/3,M2=(L+R*2)/3;
if(poly[M1](x)>poly[M2](x))
R=M2;
else
L=M1;
}
long long Ans=0;
for(int i=L;i<=R;++i)
Enlarge(Ans,poly[i](x));
fout<<Ans<<'\n';
}
}
int main() {
int T;fin>>T;
for(int ks=1;ks<=T;++ks) {
printf("Case #%d:\n",ks);
Work();
}
return 0;
}