CF932F Escape Through Leaf 题解

dqa2022 · 2019-10-24 10:44:24 · 题解

一个显然的DP，方程就不再赘述了，前人之述备矣。

我写了一发李超线段树合并的做法。大致过程就是在合并线段树的时候先合并结构，最后再把根节点的信息合并起来。

看别人的题解，很多神仙好像要么不会证明复杂度，要么认为是O(n\log^2 n)的（值域同阶）。

通过一些思考，我认为其复杂度为O(n\log n)的。下面给出大致的证明：

• 现在仅研究李超线段树合并的复杂度，其他部分复杂度显然不会超过O(n\log n)；

• 在动态开点的李超线段树中，每个点都恰好保存了一条直线的信息，并且每条直线的信息最多在一个点被记录。熟悉基础李超树的神仙们应该能够通过李超线段树的实现得出这个结论；

• 定义一条直线的深度为记录它信息的节点的深度，特别地，如果一条直线的信息消失了，那么它的深度为maxdep+1。对于两个子树都不为空的合并过程，更新答案即合并根节点的直线信息的过程要么就是把某条直线的深度直接设为maxdep+1，要么就是把一条直线的深度++。根据势能分析，这里最多进行O(n\times maxdep)次，即O(n \log n)次。

#include<cstdio>
#include<algorithm>
#include<cctype>
using namespace std;
#define G getchar()
int read()
{
    int x=0; bool flg=false; char ch=G;
    for (;!isdigit(ch);ch=G) if (ch=='-') flg=true;
    for (;isdigit(ch);ch=G) x=(x<<3)+(x<<1)+(ch^48);
    return flg?-x:x;
}
const int Base=1e5,MAXW=2e5;
typedef long long ll;
const ll INF=0x7fffffffffffffffLL;

int n,a[100010],b[100010];
ll dp[100010];
struct Rec{
    ll b;
    int k;
}rec[100010];
ll getval(int id,int pos)
{
    pos-=Base;
    return 1LL*pos*rec[id].k+rec[id].b;
}
struct Edge{
    int to,nxt;
}edge[200010];
int cnt=1,last[100010];
inline void addedge(int x,int y)
{
    edge[++cnt]=(Edge){y,last[x]},last[x]=cnt;
    edge[++cnt]=(Edge){x,last[y]},last[y]=cnt;
}
#define mid (l+r>>1)
struct Node{
    int lson,rson,id;
}node[100010];
int idtot,rt[100010];
void update(int &cur,int l,int r,int y)
{
    if (!cur) return node[cur=y]=(Node){0,0,node[y].id},void();
    if (getval(node[cur].id,l)>=getval(node[y].id,l)&&getval(node[cur].id,r)>=getval(node[y].id,r))
        return node[cur].id=node[y].id,void();
    if (getval(node[cur].id,l)<=getval(node[y].id,l)&&getval(node[cur].id,r)<=getval(node[y].id,r))
        return;
    int &a=node[cur].id,&b=node[y].id;
    if (rec[a].k<rec[b].k)
        if (getval(a,mid)>getval(b,mid)) swap(a,b),update(node[cur].rson,mid+1,r,y);
        else update(node[cur].lson,l,mid,y);
    else
        if (getval(a,mid)>getval(b,mid)) swap(a,b),update(node[cur].lson,l,mid,y);
        else update(node[cur].rson,mid+1,r,y);
}
int merge(int x,int y,int l,int r)
{
    if (!x||!y) return x|y;
    if (l==r) return getval(node[x].id,l)>getval(node[y].id,l)?y:x;
    node[x].lson=merge(node[x].lson,node[y].lson,l,mid);
    node[x].rson=merge(node[x].rson,node[y].rson,mid+1,r);
    update(x,l,r,y);
    return x;
}
ll query(int cur,int l,int r,int pos)
{
    if (!cur) return INF;
    ll res=getval(node[cur].id,pos);
    if (l==r) return res;
    if (pos<=mid) return min(res,query(node[cur].lson,l,mid,pos));
    return min(res,query(node[cur].rson,mid+1,r,pos));
}
#undef mid
void dfs(int cur,int fat)
{
    for (int i=last[cur];i;i=edge[i].nxt)
        if (edge[i].to^fat)
            dfs(edge[i].to,cur),rt[cur]=merge(rt[cur],rt[edge[i].to],0,MAXW);
    if (rt[cur]) dp[cur]=query(rt[cur],0,MAXW,a[cur]+Base);
    rec[cur]=(Rec){dp[cur],b[cur]};
    node[++idtot]=(Node){0,0,cur};
    update(rt[cur],0,MAXW,idtot);
}
int main()
{
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=1;i<=n;i++) b[i]=read();
    for (int i=2;i<=n;i++) addedge(read(),read());
    dfs(1,0);
    for (int i=1;i<=n;i++) printf("%I64d ",dp[i]); putchar('\n');
    return 0;
}

如果有任何错漏，敬请批评指正！愿多交流学习。