WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
HDU 5956 The Elder
HDU 5956 The Elder

题目大意

给定有根树,根节点为1号店,每条边边权为W_i。每个点到根节点的消耗等于将这个点到根节点的路径分成若干段,假定为k,每段的路径和为Q_i,那么总消耗为(k-1)\cdot P +\sum_{i=1}^k Q_i^2

题解

DP转移方程为:DP[i]=max{DP[j]+(dis[i]-dis[j])^2}+P,其中dis[x]为节点x到根节点的距离,ji的祖先。
可以使用斜率优化DP,推一推公式,当前要转移节点为x,假设pq的祖先,如果从q转移比从p转移要优,那么就满足条件:

\begin{aligned}
DP[p]+(dis[x]-dis[p])^2+P &> DP[q]+(dis[x]-dis[q])^2+P \\
DP[p]+dis[p]^2-2\cdot dis[x]\cdot dis[p] &> DP[q]+dis[q]^2-2\cdot dis[x]\cdot dis[q] \\
(DP[p]+dis[p]^2)-(DP[q]+dis[q]^2) &> 2\cdot dis[x]\cdot (dis[p]-dis[q]) \\
\frac{(DP[p]+dis[p]^2)-(DP[q]+dis[q]^2)}{dis[p]-dis[q]} &< 2\cdot dis[x] \\
\end{aligned}

根据条件可以发现,本题可以使用单调队列优化到O(1)

但是本题是在树上进行的,所以我们需要在DFS的过程中需要支持回溯,所以使用一个栈记录每个节点对队列的修改过程,然后回溯的时候恢复就行了。

代码

#include <cstdio>
#include <stack>
#define LL long long
#define sqr(x) (1LL*(x)*(x))
#define PII pair<int, int>
#define mp(x, y) make_pair(x, y)
using namespace std;

const int MAXN=1e5+50;

struct Edge{
    int v, nxt, w;
    Edge(){}
    Edge(int v0, int n0, int w0){ v=v0; nxt=n0; w=w0; }
}e[MAXN*2];
int head[MAXN], nume, n, P;

inline void addEdge(int u, int v, int w){
    e[++nume]=Edge(v, head[u], w);
    head[u]=nume;
    e[++nume]=Edge(u, head[v], w);
    head[v]=nume;
}

LL ans, dp[MAXN];
int dis[MAXN];
int que[MAXN], que_head, que_tail;

inline LL getDeltaY(int i, int j){ return dp[i]+sqr(dis[i])-dp[j]-sqr(dis[j]); }
inline LL getDeltaX(int i, int j){ return dis[i]-dis[j]; }
inline LL getValue(int x, int i){ return dp[i]+sqr(dis[x]-dis[i])+P; }
void dfs(int x, int from){
    stack<PII> stk;
    if (x!=1){
        while(que_head<que_tail && getDeltaY(que[que_head], que[que_head+1])>2LL*dis[x]*getDeltaX(que[que_head], que[que_head+1])) stk.push(mp(0, que[que_head])), ++que_head;
        dp[x]=getValue(x, que[que_head]);
        //printf("%d <= %d = %lld\n", x, que[que_head], dp[x]);
        while(que_head<que_tail && getDeltaY(que[que_tail], x)*getDeltaX(que[que_tail-1], que[que_tail])<getDeltaY(que[que_tail-1], que[que_tail])*getDeltaX(que[que_tail], x))
            stk.push(mp(1, que[que_tail])), --que_tail;
    }
    que[++que_tail]=x;

    ans=max(ans, dp[x]);
    for (int i=head[x]; i; i=e[i].nxt){
        int v=e[i].v, w=e[i].w;
        if (v==from) continue;
        dis[v]=dis[x]+w;
        dfs(v, x);
    }

    --que_tail;
    while(!stk.empty()){
        int op=stk.top().first, v=stk.top().second; stk.pop();
        if (op==0) que[--que_head]=v;
        if (op==1) que[++que_tail]=v;
    }
}

inline void solve(int T){
    scanf("%d%d", &n, &P);
    for (int i=1; i<=n; i++) head[i]=0; nume=0;
    for (int i=1; i<n; i++){
        int x, y, w; scanf("%d%d%d", &x, &y, &w);
        addEdge(x, y, w);
    }

    ans=que_head=que_tail=0;
    dp[1]=-P;
    dfs(1, 0);

    printf("%lld\n", ans);
}

int main(){
    // freopen("in.txt", "r", stdin);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

HDU 5956 The Elder
题目大意 给定有根树,根节点为1号店,每条边边权为$W_i$。每个点到根节点的消耗等于将这个点到根节点的路径分成若干段,假定为$k$,每段的路径和为$Q_i$,那么总消耗为$(k-1)\cdot P +\…
扫描二维码继续阅读
2018-10-09
<--! http2https -->