/* 樹上斜率優化 一開始想的是構造出一個序列 轉化成一般的dp但是可能被卡 掃把狀的樹的話可能變成n*n 其實可以直接在樹上維護這個單調隊列 dfs雖然搞得是一棵樹,但是每次都是dfs到的都是一個序列 雖然題目說的是從節點到1號 但是我們從1到節點也是一樣搞 關鍵是dfs回溯的時候怎么把改掉的序列改回去 比如當前是u 隊列里面從hea到tai 我們搞到v1 搞v1的時候 會從隊首扔掉幾個斜率小的 到時回溯回來的時候 hea 和tai 是隨著狀態存到棧里的 問題不大 q不變不影響 但是 把v1扔進去的時候 會可能先把隊尾扔幾個 這就問題大了有點慌 因為我們后面要用到這些東西 倘若我們記下隊尾的元素 搞完子樹的事情再弄回去 便好了 */ #include<cstdio> #include<cstring> #include<iostream> #define maxn 100010 #define ll long long using namespace std; int T,n,p,num,head[maxn],q[maxn]; ll s[maxn],ans,f[maxn]; struct node{int v,t,pre; }e[maxn*2]; void Add(int from,int to,int dis){num++;e[num].v=to;e[num].t=dis;e[num].pre=head[from];head[from]=num; } void dfs(int now,int from,ll dis){s[now]=dis;for(int i=head[now];i;i=e[i].pre){int v=e[i].v;if(v==from)continue;dfs(v,now,dis+e[i].t);} } ll X(int i){return s[i]; } ll Y(int i){return f[i]+s[i]*s[i]; } ll Dx(int i,int j){return X(i)-X(j); } ll Dy(int i,int j){return Y(i)-Y(j); } void Dfs(int now,int from,int hea,int tai){int pre=-1;if(now!=1){while(hea+1<tai&&Dy(q[hea+2],q[hea+1])<=2*s[now]*Dx(q[hea+2],q[hea+1]))hea++;int j=q[hea+1];f[now]=min(f[now],f[j]+(s[now]-s[j])*(s[now]-s[j])+p);while(hea+1<tai&&Dy(now,q[tai])*Dx(q[tai],q[tai-1])<=Dy(q[tai],q[tai-1])*Dx(now,q[tai]))tai--;pre=q[++tai];q[tai]=now;}ans=max(ans,f[now]);for(int i=head[now];i;i=e[i].pre){int v=e[i].v;if(v==from)continue;Dfs(v,now,hea,tai);}if(pre!=-1)q[tai]=pre; } int main(){scanf("%d",&T);while(T--){num=0;ans=0;memset(head,0,sizeof(head));memset(q,0,sizeof(q));scanf("%d%d",&n,&p);int u,v,t;for(int i=1;i<n;i++){scanf("%d%d%d",&u,&v,&t);Add(u,v,t);Add(v,u,t);}dfs(1,0,0);for(int i=1;i<=n;i++)f[i]=s[i]*s[i];Dfs(1,0,0,0);printf("%lld\n",ans);}return 0; }

?

轉載于:https://www.cnblogs.com/yanlifneg/p/9439035.html

總結

以上是生活随笔為你收集整理的The Elder HDU - 5956的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。