Codeforces Round #503 (by SIS, Div. 1)E. Raining season

题意:给一棵树每条边有a,b两个值,给你一个m,表示从0到m-1,假设当前为i,那么每条边的权值是a*i+b,求该树任意两点的最大权值

题解:首先我们需要维护出(a,b)的凸壳,对于每个i在上面三分即可,点对用树分治维护,假设当前重心是u,那么把u的直接儿子挨个合并凸壳,这一过程用闵可夫斯基和维护,set启发式合并.
//#pragma GCC optimize(2)

//#pragma GCC optimize(3)

//#pragma GCC optimize(4)

//#pragma GCC optimize("unroll-loops")

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>

#define fi first

#define se second

#define db double

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define ld long double

//#define C 0.5772156649

//#define ls l,m,rt<<1

//#define rs m+1,r,rt<<1|1

#define pll pair<ll,ll>

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define ull unsigned long long

//#define base 1000000000000000000

#define fin freopen("a.txt","r",stdin)

#define fout freopen("a.txt","w",stdout)

#define fio ios::sync_with_stdio(false);cin.tie(0)

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}

inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}

template<typename T>inline T const& MAX(T const &a,T const &b){return a>b?a:b;}

template<typename T>inline T const& MIN(T const &a,T const &b){return a<b?a:b;}

inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}

inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}

using namespace std;

const ull ba=233;

const db eps=1e-5;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=100000+10,maxn=100000+10,inf=0x3f3f3f3f;

struct FastIO {

    static const int S = 1e7;

    int wpos;

    char wbuf[S];

    FastIO() : wpos(0) {}

    inline int xchar() {

        static char buf[S];

        static int len = 0, pos = 0;

        if (pos == len)

            pos = 0, len = fread(buf, 1, S, stdin);

        if (pos == len) exit(0);

        return buf[pos++];

    }

    inline int xuint() {

        int c = xchar(), x = 0;

        while (c <= 32) c = xchar();

        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';

        return x;

    }

    inline int xint()

    {

        int s = 1, c = xchar(), x = 0;

        while (c <= 32) c = xchar();

        if (c == '-') s = -1, c = xchar();

        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';

        return x * s;

    }

    inline void xstring(char *s)

    {

        int c = xchar();

        while (c <= 32) c = xchar();

        for (; c > 32; c = xchar()) * s++ = c;

        *s = 0;

    }

    inline void wchar(int x)

    {

        if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;

        wbuf[wpos++] = x;

    }

    inline void wint(ll x)

    {

        if (x < 0) wchar('-'), x = -x;

        char s[24];

        int n = 0;

        while (x || !n) s[n++] = '0' + x % 10, x /= 10;

        while (n--) wchar(s[n]);

        wchar('\n');

    }

    inline void wstring(const char *s)

    {

        while (*s) wchar(*s++);

    }

    ~FastIO()

    {

        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;

    }

} io;

struct edge{int to,Next,a,b;}e[maxn<<1];

int cnt,head[N],sz[N],zx[N],n;

pll dis[N];

bool vis[N];

void init(){cnt=0;memset(head,-1,sizeof head);memset(vis,0,sizeof vis);}

void add(int u,int v,int a,int b){e[cnt].to=v;e[cnt].a=a;e[cnt].b=b;e[cnt].Next=head[u];head[u]=cnt++;}

void dfssz(int u,int f,int &sum)

{

    sum++;sz[u]=1;

    for(int i=head[u];~i;i=e[i].Next)

    {

        int x=e[i].to;

        if(x==f||vis[x])continue;

        dfssz(x,u,sum);sz[u]+=sz[x];

    }

}

void dfszx(int u,int f,int sum,int &ans,int &id)

{

    zx[u]=sum-sz[u];

    for(int i=head[u];~i;i=e[i].Next)

    {

        int x=e[i].to;

        if(x==f||vis[x])continue;

        dfszx(x,u,sum,ans,id);

        zx[u]=max(zx[u],sz[x]);

    }

    if(ans>zx[u]){ans=zx[u],id=u;}

}

int findzx(int root)

{

    int sum=0;

    dfssz(root,-1,sum);

    int ans=inf,id=0;

    dfszx(root,-1,sum,ans,id);

    return id;

}

struct Point {

    ll x, y;

    Point(ll x = 0, ll y = 0) : x(x), y(y) {}

};

typedef Point Vector;

Point operator + (Vector A, Vector B) {return Point(A.x + B.x, A.y + B.y);}

Point operator - (Vector A, Vector B) {return Point(A.x - B.x, A.y - B.y);}

bool operator == (const Vector &A, const Point &B) {return A.x == B.x&& A.y == B.y;}

bool operator < (const Vector &A, const Vector &B) {return A.y < B.y || (A.y == B.y && A.x < B.x);}

ll Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;}

int ConvexHull(Point *p, int n, Point *ch) {

    sort(p, p + n);

    int m = 0;

    for(int i = 0; i < n; i++) {

        while(m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) m--;

        ch[m++] = p[i];

    }

    int k = m;

    for(int i = n - 2; i >= 0; i--) {

        while(m > k && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) m--;

        ch[m++] = p[i];

    }

    return n==1?m:m - 1;

}

int minkowski(Point *a,int &n,Point *b,int &m,Point *c,Point *d)

{

    int top=0;

    if(n<=2||m<=2)

    {

        for(int i=0;i<n;i++)for(int j=0;j<m;j++)

            d[top++]=a[i]+b[j];

        top=ConvexHull(d,top,c);

        return top;

    }

    c[top++]=a[0]+b[0];

    for(int i=0,j=0;i<n||j<m;)

    {

        Point p1=a[i%n]+b[(j+1)%m],p2=a[(i+1)%n]+b[j%m];

        if(Cross(p1-c[top-1],p2-c[top-1])>=0)c[top++]=p1,++j;

        else c[top++]=p2,++i;

    }

    return top-1;

}

Point a[N*40],b[N],c[N*4],d[N*4],ans[N*40];

vector<Point>v[N];

int top,la,lb;

void dfsdis(int u,int f,int root)

{

    int num=0;

    for(int i=head[u];~i;i=e[i].Next)

    {

        int x=e[i].to;

        if(x==f||vis[x])continue;

        num++;

        dis[x].fi=dis[u].fi+e[i].a;

        dis[x].se=dis[u].se+e[i].b;

        dfsdis(x,u,root);

    }

    if(num==0)v[root].pb({dis[u].fi,dis[u].se});

}

void gao(int x)

{

    la=0;

    for(int i=0;i<v[x].size();i++)a[la++]=v[x][i];

    lb=ConvexHull(a,la,b);v[x].clear();

    for(int i=0;i<lb;i++)v[x].pb(b[i]);

}

void solve(int root)

{

    int p=findzx(root);

    v[0].clear();v[0].pb({0,0});

    set<pii>s;s.clear();s.insert(mp(v[0].size(),0));

    for(int i=head[p];~i;i=e[i].Next)

    {

        int x=e[i].to;if(vis[x])continue;

        v[x].clear();

        dis[x]=mp(e[i].a,e[i].b);dfsdis(x,p,x);

        gao(x);s.insert(mp(v[x].size(),x));

    }

    while(s.size()>=2)

    {

        int x=s.begin()->se;s.erase(s.begin());

        int y=s.begin()->se;s.erase(s.begin());

        la=lb=0;

        for(int i=0;i<v[x].size();i++)a[la++]=v[x][i];

        for(int i=0;i<v[y].size();i++)b[lb++]=v[y][i];

        int te=minkowski(a,la,b,lb,c,d);

        for(int i=0;i<te;i++)ans[top++]=c[i];

        for(int i=0;i<v[y].size();i++)v[x].pb(v[y][i]);v[y].clear();

        gao(x);s.insert(mp(v[x].size(),x));

    }

    vis[p]=1;

    for(int i=head[p];~i;i=e[i].Next)

    {

        int x=e[i].to;

        if(vis[x])continue;

        solve(e[i].to);

    }

}

int main()

{

    int n=io.xint(),m=io.xint();

    init();

    for(int i=1;i<n;i++)

    {

        int u=io.xint(),v=io.xint(),a=io.xint(),b=io.xint();

        add(u,v,a,b);add(v,u,a,b);

    }

    solve(1);

    top=ConvexHull(ans,top,a);

    for(int i=0;i<m;i++)

    {

        int l=-1,r=top;

        while(l<r-6)

        {

            int m=(l+r)>>1,m1=(m+r)>>1;

            if(a[m].x*i+a[m].y>a[m1].x*i+a[m1].y)r=m1;

            else l=m;

        }

        ll ma=0;

        for(int j=max(0,l-10);j<min(top,l+10);j++)ma=max(ma,a[j].x*i+a[j].y);

        io.wint(ma);

    }

    return 0;

}

/********************

********************/
巴特西

Codeforces Round #503 (by SIS, Div. 1)E. Raining season

最新文章

热门文章
