解析

好題
意思就是我沒做出來
稍微分析一下就可以發現加邊的位置始終是一樣的
換句話說詢問完全可以O1
關鍵就是找到這條邊加在哪里

一開始我完全把這道題看成了徹頭徹尾的數據結構題
容易想到二分答案
然后上個樹狀樹組搞一搞就行了
但是遇到一個關鍵的問題
它無法解決加邊必須是非樹邊的問題
于是又搞巴搞巴整了個線段樹并且把離散化的去重干掉，開始亂搞
然后就T了…
本來線段樹常數就大我的那個東西暴力修改還自帶好幾倍常數…
倆log根本過不去3e5

無奈之下看了題解
真的很巧妙
復雜度和實現難度雙重碾壓我qwq
把1-n的鏈提出來
然后分類一下就迎刃而解了
upd:代碼有問題！（CF沒卡掉…但是顯然是假的）
求鏈上的min時不一定相鄰，而是應該提出來一些東西維護一個最小值

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define il inline #define debug(a,b) fprintf(stderr,a,b) const int N=3e5+100; const int M=3e6+100; const int mod=998244353; inline ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n,m; int fi[N],cnt; struct node{int to,nxt,w; }p[N<<1]; inline void addline(int x,int y,int w){p[++cnt]=(node){y,fi[x],w};fi[x]=cnt;return; } ll ans=3e14; int fa[N],siz[N],hson[N]; ll dis[N]; void dfs(int x,int f){fa[x]=f;siz[x]=1;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==f) continue;dis[to]=dis[x]+p[i].w;dfs(to,x);siz[x]+=siz[to];}return; } ll add[N]; void find(int x){if(!x) return;if(fa[fa[x]]){ans=min(ans,dis[x]-dis[fa[fa[x]]]);}hson[fa[x]]=x;if(siz[x]-siz[hson[x]]-1>=2){ans=0;return;}for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==fa[x]||to==hson[x]) continue;add[x]=p[i].w;}for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to!=hson[x]) continue;if(add[x]||add[to]) ans=min(ans,1ll*p[i].w-add[x]-add[to]);}find(fa[x]); } int main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifmemset(fi,-1,sizeof(fi));cnt=-1;n=read();m=read();for(int i=1;i<n;i++){int x=read(),y=read(),w=read();addline(x,y,w);addline(y,x,w);}dfs(1,0);find(n);for(int i=1;i<=m;i++){int x=read();printf("%lld\n",dis[n]-max(0ll,ans-x));}return 0; } /* 3 1 3 1 33 2 1 1 2 3 1 3 */ 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的CF1016F:Road Projects（树形dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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