可以每一次都進行一次樹形DP，發現有很多點是沒有用的，只需要找出一些關鍵點來進行樹形DP就可以，這就用到了虛樹。可以用一個棧來維護一條鏈構建虛樹。 PS:INF一定要夠大！！！！
#include #include #include #include #include #include #include #include #include #include #define inf 1e60 #define ll long long #define N 500009 using namespace std; int sc() { int i=0,f=1; char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar(); return i*f; } ll mn[N],f[N],v[N]; int Head[N],Nxt[N],Lst[N]; int deep[N],size[N],fa[N],top[N]; int head[N],lst[N],nxt[N],S[N]; int h[N],st[N]; int n,cnt,tot,Tot,m; bool cmp(int x,int y){return S[x]size[k])k=lst[i]; if(!k)return;_dfs(k,htp); for(int i=head[x];i;i=nxt[i]) if(lst[i]!=k&&lst[i]!=fa[x]) _dfs(lst[i],lst[i]); } int Lca(int x,int y) { while(top[x]!=top[y]) { if(deep[top[x]]deep[y]?y:x; } ll dp(int x) { ll tmp=0; for(int i=Head[x];i;i=Nxt[i]) tmp+=dp(Lst[i]); Head[x]=0; return tmp?min(tmp,mn[x]):mn[x]; } void solve() { int n=sc(),top=0;Tot=0; for(int i=1;i<=n;i++)h[i]=sc(); sort(h+1,h+n+1,cmp); int tot=1; for(int i=2;i<=n;i++) if(Lca(h[tot],h[i])!=h[tot])h[++tot]=h[i]; st[++top]=1; for(int i=1;i<=tot;i++) { int now=h[i],f=Lca(h[i],st[top]); while(1) { if(deep[f]>=deep[st[top-1]]) { Insert(f,st[top--]); if(st[top]!=f)st[++top]=f; break; } Insert(st[top-1],st[top]);top--; } if(st[top]!=now)st[++top]=now; } while(--top)Insert(st[top],st[top+1]); printf("%lld\n",dp(1)); } int main() { //freopen("2286.in","r",stdin); //freopen("2286.out","w",stdout); n=sc(); for(int i=1;i
[cpp] /*
利用STL自己實現split 函數(常用，簡單，直觀)
C++字符串常量，字符串常量 C++字符串常量
程序： [cpp] // 定點小數補碼一位
C++02.訪問控制，02訪問控制1.class是struc
記事本中寫c/c++程序在Windows下執行 A
