Two

　　求用兩個人從根開始走完整個樹所用的最短路程.

　　情況分為兩種:

　　1.兩個人從根分開走并不再會和；

　　2.讓一個人走完其它子樹,并兩個人會和在未走的子樹的根，得到一個子問題.

　　要用到一個結論:

　　　　從一個點遍歷整棵樹走的最小路徑=樹邊長和*2-樹直徑.

two #include<stdio.h> #include<string.h> #include<vector> #include<algorithm> #define min(a,b) (a)<(b)?(a):(b) #define max(a,b) (a)>(b)?(a):(b) #define maxn 100010 using namespace std; const int inf=500000001; typedef struct nd {int v;int d; }nd; vector<nd>e[maxn]; int n,s; int mxl[maxn]; int td[maxn]; int dp[maxn]; void input() {int i;int a,b,c;nd tmp;for(i=1;i<n;i++){scanf("%d%d%d",&a,&b,&c);tmp.v=b;tmp.d=c;e[a].push_back(tmp);tmp.v=a;tmp.d=c;e[b].push_back(tmp);} } void init() {int i;for(i=1;i<=n;i++)e[i].clear();memset(mxl,-1,sizeof(mxl));memset(td,-1,sizeof(td));memset(dp,-1,sizeof(dp)); } int init_td(int fa,int cur) {int i,res=0;nd ck;for(i=0;i<e[cur].size();i++)if(e[cur][i].v!=fa){ck=e[cur][i];res+=init_td(cur,e[cur][i].v)+e[cur][i].d;}return td[cur]=res; } int init_mxl(int fa,int cur) {int i,res=0;for(i=0;i<e[cur].size();i++)if(e[cur][i].v!=fa){int tmp=init_mxl(cur,e[cur][i].v);res=max(res,tmp+e[cur][i].d);}return mxl[cur]=res; } bool cmp(const nd& a, const nd& b){return mxl[a.v]+a.d > mxl[b.v]+b.d; } int dfs(int fa,int cur) {int i,res,cut=0;nd ck;res=td[cur]*2-mxl[cur];for(i=0;i<e[cur].size();i++)if(e[cur][i].v != fa){ck=e[cur][i];int t=td[cur]-td[e[cur][i].v]-e[cur][i].d;int tmp=dfs(cur,e[cur][i].v)+t*2+e[cur][i].d*2;res=min(res,tmp);}for(i=0;i<e[cur].size();i++)if(e[cur][i].v != fa){cut+=mxl[e[cur][i].v]+e[cur][i].d;break;}for(i++;i<e[cur].size();i++)if(e[cur][i].v != fa){cut+=mxl[e[cur][i].v]+e[cur][i].d;break;}res=min(td[cur]*2-cut,res);return dp[cur]=res; } void solv() {int i;init_td(0,s);init_mxl(0,s);for(i=1;i<=n;i++)sort(e[i].begin(),e[i].end(),cmp);dfs(0,s);printf("%d\n",dp[s]); } int main() {while(scanf("%d%d",&n,&s)!=EOF){init();input();solv();}return 0; }

　　

　　Binary Apple Tree

　　給一個二叉樹,每個點有它的權值,剪去一些邊保留q條邊,求最大能保留多少權值.(要保證剪完后仍然是一顆樹)

　　這是個簡單的問題:

　　dp[i][j]為以i為根,保留j條邊的最大權值.

　　dp[i][j]=max{dp[ls][t]+dp[rs][j-2-t]}

　　但是非常具有啟發性：

　　如果將二叉樹換為普通樹,將得到問題的拓展版.

　　假設普通樹有k個孩子,可以將問題看做容量為q,物品數為k*q的01背包

　　

樹形背包 1 void dfs(int fa,int cur) 2 { 3 int i,j,k; 4 for( i=0; i<e[cur].size();i++) 5 if(e[cur][i] != fa){ 6 int v=e[cur][i]; 7 dfs(cur,v); 8 for(j=q;j>0;j--) 9 for(k=0;k<j;k++) 10 dp[cur][j]=max(dp[cur][j],dp[cur][j-k-1]+dp[v][k]); 11 } 12 } 13 /* 14 注意更新dp[][]的兩層循環不能顛倒成 15 for(k=0;k<q;k++) 16 for(j=q;j>0;j--) 17 if(j-k>=0) 18 dp[cur][j]=max(dp[cur][j],dp[cur][j-k-1]+dp[v][k]); 19 因為dp【cur][j-k-1]更新dp[cur][j]的時候,可能已經被dp[v][]更新過了, 20 于是dp[v][]被加過兩次. 21 */

?

　　因為遍歷樹是有順序的,遍歷到u的兒子v_n時v₁~v_n-1都已經用來更新過dp[u][]而v_n及其以后的兒子都沒有用來更新,

　　所以這樣dp是清楚的,不會產生混亂和重復.

?

　　Apple Tree

?

　　給一個帶權的普通樹,求走k步能獲得的最大權值.

　　將dp分為兩部分:

　　dp[0][i][j]從i點出發走j步并回來獲得的最大權值

　　dp[1][i][j]從i點出發走j步不回來能獲得的最大權值.

　　然后用類似?Binary Apple Tree?的方式更新.

　　

Apple tree #include<stdio.h> #include<string.h> #include<vector> #define maxn 222 #define max(a,b) (a)>(b)?(a):(b) using namespace std; vector<int> e[maxn]; int n,m,d[2][maxn][maxn],val[maxn],ans=-1; void input() {int i,u,v;for(i=1;i<=n;i++)scanf("%d",&val[i]);for(i=1;i<n;i++){scanf("%d%d",&u,&v);e[u].push_back(v);e[v].push_back(u);} } void DP(int fa,int cur,int maxm) {int i,j,k,v;d[0][cur][0]=val[cur],d[1][cur][0]=val[cur];for(i=0;i<e[cur].size();i++)if(e[cur][i]!=fa){v=e[cur][i];DP(cur,v,maxm-1);for(j=maxm;j>=0;j--)for(k=0;k<j;k++){if(j-2-k>=0 && d[0][cur][j-k-2]>=0 && d[0][v][k]>=0)d[0][cur][j]=max(d[0][cur][j],d[0][cur][j-2-k]+d[0][v][k]);if(j-1-k>=0 && d[1][v][k]>=0 && d[0][cur][j-1-k]>=0)d[1][cur][j]=max(d[1][cur][j],d[1][v][k]+d[0][cur][j-1-k]);if(j-2-k>=0 && d[1][cur][j-2-k]>=0 && d[0][v][k]>=0)d[1][cur][j]=max(d[1][cur][j],d[1][cur][j-2-k]+d[0][v][k]);}} } void flush() {int i;for(i=0;i<=n;i++)e[i].clear(); } int main() {//freopen("test.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){input();memset(d,-1,sizeof(d));ans=-1;DP(0,1,m);for(int i=0;i<=m;i++)for(int j=0;j<2;j++){ans=max(ans,d[j][1][i]);}printf("%d\n",ans);flush();}return 0; }

?

　　Network

　　給n個點的樹,和m條新加的邊,問有多少種方式,刪掉原樹的一條邊和新加的一條邊使圖分為兩部分.

　　每加上一條新邊,都會產生環,如果原樹中有一條邊只在一個環中,那么刪掉它和對應的新邊就會使圖分為兩部分.

　　當然,還要統計出原樹中未成為環的邊,因為只需刪掉它們中一條就可以使圖分為兩部分.

　　統計的方式十分巧妙,用dp[v]表示點v到他父親的邊,如果加入的邊為e(u,v),

　　那么　　dp[u]++,　　dp[v]++,　　dp[lca(u,v)]-=2;　　最后深度遍歷一遍,得到所有邊的值.

　　其實仔細想想也不難發現它的正確性.

　　這題的重點是發現分類標準,和找到統計方式.

　　

Network 1 #include<stdio.h> 2 #include<string.h> 3 #include<vector> 4 #include<math.h> 5 #define maxn 100100 6 using namespace std; 7 struct edge{ 8 int v,nxt; 9 };edge e[maxn*2]; 10 int first[maxn*2],ne; 11 int dgr[maxn*2],idx[maxn],nd[maxn*2],sz,rmq[maxn*2][20],vis[maxn]; 12 int f[maxn],n,m; 13 14 void add_edge(int u,int v){ 15 e[ne].v=v;e[ne].nxt=first[u]; 16 first[u]=ne++; 17 } 18 void input() 19 { 20 int i,v,u; 21 ne=0; 22 memset(first,-1,sizeof(first)); 23 for(i=1;i<n;i++){ 24 scanf("%d%d",&u,&v); 25 add_edge(u,v); 26 add_edge(v,u); 27 } 28 } 29 void dfs(int cur,int deep) 30 { 31 int i; 32 dgr[++sz]=deep;nd[sz]=cur; 33 idx[cur]=sz; 34 for(i=first[cur];i!=-1;i=e[i].nxt) 35 if(!vis[e[i].v]){ 36 vis[e[i].v]=1; 37 dfs(e[i].v,deep+1); 38 dgr[++sz]=deep; nd[sz]=cur; 39 } 40 } 41 void init_rmq() 42 { 43 int i,j,lmt,lft,rgt; 44 for(i=1;i<=sz;i++)rmq[i][0]=i; 45 for(i=1;(1<<i)<=sz;i++) 46 for(j=1;j+(1<<i)-1<=sz;j++) 47 { 48 rmq[j][i]=rmq[j][i-1]; 49 lft=rmq[j][i-1]; 50 rgt=rmq[j+(1<<(i-1))][i-1]; 51 if(dgr[lft]<dgr[rgt])rmq[j][i]=lft; 52 else rmq[j][i]=rgt; 53 } 54 } 55 int LCA(int l,int r) 56 { 57 int rg,k,lft,rgt; 58 if(l>r)swap(l,r); 59 rg=r-l+1; 60 k=log((double)rg)/log(2.0); 61 lft=rmq[l][k]; 62 rgt=rmq[r-(1<<k)+1][k]; 63 if(dgr[lft]<dgr[rgt])return nd[lft]; 64 return nd[rgt]; 65 } 66 int statis(int cur) 67 { 68 int i; 69 for(i=first[cur];i!=-1;i=e[i].nxt) 70 if(!vis[e[i].v]){ 71 vis[e[i].v]=1; 72 f[cur]+=statis(e[i].v); 73 } 74 return f[cur]; 75 } 76 77 int main() 78 { 79 int u,v,lca; 80 int ans; 81 //freopen("test","r",stdin); 82 scanf("%d%d",&n,&m); 83 input(); 84 sz=0; 85 memset(vis,0,sizeof(vis));vis[1]=1; 86 dfs(1,0); 87 init_rmq(); 88 memset(f,0,sizeof(f)); 89 for(int i=0;i<m;i++){ 90 scanf("%d%d",&u,&v); 91 lca=LCA(idx[u],idx[v]); 92 f[u]++;f[v]++;f[lca]-=2; 93 } 94 memset(vis,0,sizeof(vis));vis[1]=1; 95 statis(1); 96 ans=0; 97 for(int i=2;i<=n;i++) 98 if(f[i]==0 || f[i]==1){ 99 if(f[i]==0)ans+=m; 100 if(f[i]==1)ans++; 101 } 102 printf("%d\n",ans); 103 return 0; 104 }

?

　　Journey

　　問題可以描述為:旅人在樹的k點,要訪問一系列點,求最小路程.

　　造樹就行了,方法很多,我是用bfs不斷找要訪問點的父親,也可以dfs一遍用dp[v]表示從v點下去是否有需要訪問的點.

　　這題很惡心地卡了stl,害我wa了8次,看來以后使用stl的時候要小心.

　　

Journey 1 #include<stdio.h> 2 #include<string.h> 3 #include<queue> 4 #include<vector> 5 #define maxn 55555 6 using namespace std; 7 struct edge{ 8 int v,nxt; 9 }; 10 edge e[maxn*2],t[maxn*2]; 11 int he[maxn*2],ht[maxn*2],ne,nt,d1[maxn*2],d2[maxn*2]; 12 13 int n,k,vis[maxn],fa[maxn],rcd[maxn],bg,len[maxn],total; 14 queue<int>q; 15 void add_edge_e(int u,int v,int dist) 16 { 17 e[ne].v=v;e[ne].nxt=he[u];d1[ne]=dist; 18 // printf("d1[%d]=%d\n",ne,d1[ne]); 19 he[u]=ne++; 20 } 21 void add_edge_t(int u,int v,int dist) 22 { 23 t[nt].v=v;t[nt].nxt=ht[u];d2[nt]=dist; 24 // printf("d2[%d]=%d\n",nt,d2[nt]); 25 ht[u]=nt++; 26 } 27 void input() 28 { 29 int i,u,v,dist; 30 memset(he,-1,sizeof(he));ne=0; 31 memset(ht,-1,sizeof(ht));nt=0; 32 for(i=1;i<n;i++){ 33 scanf("%d%d%d",&u,&v,&dist); 34 add_edge_e(u,v,dist); 35 add_edge_e(v,u,dist); 36 } 37 scanf("%d",&k); 38 for(i=1;i<=k;i++)scanf("%d",&vis[i]); 39 } 40 void dfs(int f,int cur) 41 { 42 int i; 43 fa[cur]=f; 44 for(i=he[cur];i!=-1;i=e[i].nxt) 45 if(e[i].v!=f){ 46 // printf("fa=%d cur=%d dist=%d\n",cur,e[cur][i],d1[cur][i]); 47 dfs(cur,e[i].v); 48 } 49 } 50 int find_dist(int cur,int fa_cur) 51 { 52 int i; 53 for(i=he[fa_cur];i!=-1;i=e[i].nxt){ 54 // printf("e[%d].v=%d cur=%d\n",i,e[i].v,cur); 55 if(e[i].v==cur){ 56 return d1[i]; 57 } 58 } 59 return -1; 60 } 61 void bfs() 62 { 63 int i,cur,nxt,dist; 64 memset(rcd,0,sizeof(rcd)); 65 rcd[bg]=1; 66 for(i=1;i<=k;i++){ 67 q.push(vis[i]); 68 rcd[vis[i]]=1; 69 } 70 while(!q.empty()){ 71 cur=q.front();q.pop(); 72 nxt=fa[cur]; 73 dist=find_dist(cur,nxt); 74 total+=dist; 75 // printf("fa=%d cur=%d dist=%d\n",nxt,cur,dist); 76 add_edge_t(nxt,cur,dist); 77 if(!rcd[nxt]){ 78 rcd[nxt]=1; 79 q.push(nxt); 80 } 81 } 82 } 83 void init_len(int cur) 84 { 85 int i; 86 for(i=ht[cur];i!=-1;i=t[i].nxt){ 87 init_len(t[i].v); 88 len[cur]=max(len[cur],len[t[i].v]+d2[i]); 89 } 90 } 91 int main() 92 { 93 // freopen("test","r",stdin); 94 scanf("%d%d",&n,&bg);{ 95 input(); 96 dfs(0,bg); 97 total=0; 98 bfs(); 99 memset(len,0,sizeof(len)); 100 init_len(bg); 101 printf("%d\n",total*2-len[bg]); 102 // flush(); 103 } 104 return 0; 105 }

?

　　Computer Network

　　經典的樹形dp,求樹中以每個點v為起點的最長路徑.

　　對每個點v記錄兩個值

　　Len[0][v]:從v點出發的一條最長路徑.

　　Len[1][v]:從v點出發經過其它兒子的路徑中最長的一條.

　　然后從根開始dfs：

　　當前樹的根為u，兒子為v，

　　則len[0][v]=max{

　　　　len[0][v];

　　　　len[0][u]+d[u][v];

　　}

　　如果v在len[0][u]這條路徑上,那么要替換成len[1][u].

　　mxl[v]更新完后,更新維護len[0][v].

　　

Computer network #include<stdio.h> #include<string.h> #define max(a,b) (a)>(b)?(a):(b) #define maxn 10011 struct edge{int v,nxt,d; };edge e[maxn*2];struct nd{int d,id; };nd l[2][maxn];int hd[maxn*2],ne,n,mxl[maxn]; void add_edge(int u,int v,int d) {e[ne].v=v;e[ne].nxt=hd[u];e[ne].d=d;hd[u]=ne++; } void input() {int i,v,d;memset(hd,-1,sizeof(hd));for(i=2,ne=0;i<=n;i++){scanf("%d%d",&v,&d);add_edge(i,v,d);add_edge(v,i,d);} } void dfs1(int fa,int cur) {int i,id=0;for(i=hd[cur];i!=-1;i=e[i].nxt)if(e[i].v != fa)dfs1(cur,e[i].v);for(i=hd[cur];i!=-1;i=e[i].nxt)if(e[i].v != fa && l[0][cur].d<l[0][e[i].v].d+e[i].d)l[0][cur].d=l[0][e[i].v].d+e[i].d,id=e[i].v;l[0][cur].id=id;for(i=hd[cur];i!=-1;i=e[i].nxt)if(e[i].v!=fa && e[i].v!=id && l[1][cur].d<l[0][e[i].v].d+e[i].d)l[1][cur].d=l[0][e[i].v].d+e[i].d,l[1][cur].id=e[i].v;mxl[cur]=l[0][cur].d; } void dfs2(int fa,int cur) {int i,v,j;for(i=hd[cur];i!=-1;i=e[i].nxt)if(e[i].v!=fa){v=e[i].v;if(l[0][cur].id == v){if(l[0][v].d<l[1][cur].d+e[i].d){l[0][v].d=l[1][cur].d+e[i].d,l[0][v].id=cur;}else if(l[1][v].d<l[1][cur].d+e[i].d)l[1][v].d=l[1][cur].d+e[i].d;l[1][v].id=cur;}else if(l[0][v].d<l[0][cur].d+e[i].d){l[0][v].d=l[0][cur].d+e[i].d,l[0][v].id=cur;}dfs2(cur,e[i].v);} } int main() {int i;while(scanf("%d",&n)!=EOF){input();memset(l,0,sizeof(l));dfs1(0,1);dfs2(0,1);for(i=1;i<=n;i++)printf("%d\n",l[0][i].d);}return 0; }

　　問題可以推展為求樹的頂點v所在的最長路徑.

?

記錄下最近遇到的一些比較麻煩的樹形dp統計問題:

　　Hourai Jeweled?　　(2012多校1 by bupt)

題目給出一顆節點帶有權值,各邊有顏色的樹,并定義 '合法路徑' 為相鄰邊顏色不同的路徑.

合法路徑的權值就是路徑中各點權值的累加,求統計所有路徑的權值和.

　　我用一個含兩域的結構題保存了每個節點的信息:

　　jew[u].ne: u能傳遞給它father的路徑數.

　　jew[u[.val: u傳遞給他father的路徑的權值和

我們dfs的時候要做的事就是利用兒子節點來更新根結點的jew 和 統計各種連接情況下的權值和:

　　1. 當前節點u是路徑的末端點.

　　2.當前節點u是連接它某兩個兒子的合法路徑中的點;

　　3.當前點u是連接它某個兒子和它父親的合法路徑中的點.

1,2可以直接利用兒子節點的jew來統計,3可以轉化為它祖先的第一種情況.

Hourai Jeweled #include<stdio.h>#include<string.h>#include<vector>#include<algorithm>#define maxn 300030using namespace std;typedef long long llong;struct nd{int v,c;};struct nd2{llong val;llong ne;};vector<nd> e[maxn];nd2 jew[maxn];int n,val[maxn];llong cnt;bool cmp(const nd& a,const nd& b){return a.c <b.c;}void input(){int i,u,v,c;nd cur;for(i=1;i<=n;i++)scanf("%d",&val[i]);for(i=1;i<n;i++){scanf("%d%d%d",&u,&v,&c);cur.v=v,cur.c=c;e[u].push_back(cur);cur.v=u,cur.c=c;e[v].push_back(cur);}for(i=1;i<=n;i++)sort(e[i].begin(),e[i].end(),cmp);}void print(int fa,nd cur){printf("\n**************\n");printf("Father Edge Color:%d\n",cur.c);printf("father=%d son=%d\n",fa,cur.v);printf("Edge count=%d val=%d\n",jew[cur.v].ne,jew[cur.v].val);printf("\n**************\n");}void dfs(int col,int fa,int cur){int i,l=0;llong com=0,comedg=0;llong total=0,totedg=0;for(i=0;i<e[cur].size();i++)if(e[cur][i].v != fa){dfs(e[cur][i].c,cur,e[cur][i].v);if(e[cur][i].c != col){// print(cur,e[cur][i]);jew[cur].ne+=jew[e[cur][i].v].ne;jew[cur].val+=jew[e[cur][i].v].val;}total+=jew[e[cur][i].v].val;totedg+=jew[e[cur][i].v].ne;}cnt+=totedg*val[cur]+total;jew[cur].ne++;jew[cur].val+=jew[cur].ne*val[cur];for(i=0;i<e[cur].size();i++)if(e[cur][i].v != fa){if(e[cur][i].c != e[cur][l].c){cnt+=(totedg-comedg)*com+comedg*(total-com)+comedg*(totedg-comedg)*val[cur];total-=com;totedg-=comedg;com=0;comedg=0;l=i;}com+=jew[e[cur][i].v].val;comedg+=jew[e[cur][i].v].ne;}}void flush(){int i;for(i=1;i<=n;i++)e[i].clear();}int main(){// freopen("data.in","r",stdin);while(scanf("%d",&n)!= EOF){input();memset(jew,0,sizeof(jew));cnt=0;dfs(-1,0,1);printf("%lld\n",cnt);flush();}return 0;}

　　Holiday's Accommodatio?(2011 Chen'Du Regional Problem H, hdu 4118)

　　題目背景是來自n個城市的家庭要訪問其它家庭所在的城市,求所有家庭能移動的最大距離和,題目要求不能有兩個家庭移動到同一個城市,

并且移動過程中都是走的最短路.

　　題目的要求跟最大權匹配類似,但是數據規模巨大,直接跑匹配肯定是行不通的.

　　這個問題的統計方法很巧妙,考慮一條邊e,設它左邊有x個節點,右邊有y個節點,那么它最多被通過min(x,y) * 2次,所以用樹形dp統計出每個節點為根

的子樹的節點數就可以了.

Holiday's Accommodation #include<stdio.h> #include<string.h> #define maxn 100010 #define min(a,b) (a)<(b)?(a):(b) typedef long long llong; typedef struct Edge{int v;int nxt;llong w; }Edge;Edge e[maxn<<1]; int head[maxn<<1],n,cnte,cntp[maxn],pre[maxn],cnts; bool vis[maxn]; llong ans; void add_edge(int u,int v,llong w) {e[cnte].v=v;e[cnte].nxt=head[u];e[cnte].w=w;head[u]=cnte++; } void input() {int i,u,v;llong w;memset(head,-1,sizeof(head));cnte=0;scanf("%d",&n);for(i=1;i<n;i++){scanf("%d%d%I64d",&u,&v,&w);add_edge(u,v,w);add_edge(v,u,w);} } void init_cntp() {int cur=1,i;pre[cur]=0;memset(vis,0,sizeof(vis));memset(cntp,0,sizeof(cntp));cntp[cur]=1;vis[1]=1;while(cur){for(i=head[cur];i!=-1;)if(!vis[e[i].v]){vis[e[i].v]=1;pre[e[i].v]=cur;cur=e[i].v;cntp[cur]=1;i=head[cur];}else i=e[i].nxt;cntp[pre[cur]]+=cntp[cur];cur=pre[cur];} } void statis() {int cur=1,i;llong a,b;ans=0;pre[cur]=0;memset(vis,0,sizeof(vis));vis[cur]=1;while(cur){for(i=head[cur];i!=-1;)if(!vis[e[i].v]){vis[e[i].v]=1;a=cntp[cur]-cntp[e[i].v];b=cntp[e[i].v];ans+=(min(a,b)) * e[i].w*2;cntp[e[i].v]=cntp[cur];pre[e[i].v]=cur;cur=e[i].v;i=head[cur];}else i=e[i].nxt;cur=pre[cur];}printf("%I64d\n",ans); } int main() {int cas,t; // freopen("test.txt","r",stdin);scanf("%d",&cas);for(t=1;t<=cas;t++){printf("Case #%d: ",t);input();init_cntp();statis();}return 0; }

　　hdu用dfs會爆棧,寫成了非遞歸的形式.

轉載于:https://www.cnblogs.com/eggeek/archive/2012/07/17/2588916.html

總結

以上是生活随笔為你收集整理的【总结】树形dp的全部內容，希望文章能夠幫你解決所遇到的問題。

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