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;
}