【題目描述】給定2-3顆樹，每個邊的邊權(quán)為1，解決以下獨立的問題。

　　　　現(xiàn)在通過連接若干遍使得圖為連通圖，并且Σdis(x,y)最大，x，y只算一次。

　　　　每個點為黑點或者白點，現(xiàn)在需要刪除一些邊，使得圖中的黑點度數(shù)為奇數(shù)，白點為偶數(shù)，要求刪除的邊最多。

　　【數(shù)據(jù)范圍】 100% n<=10^5

　　首先我們來解決第一問，因為每加一條邊就可能使得若干點到其他點的距離變小，那么我們需要加盡量少的邊來使得圖連通。

　　設(shè)dis_[x]為x在x所在子樹中，x到其他所有點的距離，這個我們可以通過設(shè)dis[x]表示x到x子樹中所有點的距離和來由父節(jié)點轉(zhuǎn)移得到。

　　那么答案可以分為兩部分，分別為樹中的點對距離和跨樹的點對距離，前一個問題比較容易，可以通過dis_[x]或者計算每條邊被經(jīng)過的次數(shù)來求出。

　　那么對于兩顆樹的情況，我們就需要連接這兩棵樹中dis值最大的兩個點，假設(shè)為x，y。這樣答案就是 ? ? ?dis[x]*size[tree_y]+dis[y]*size[tree_x]+size[tree_x]*size[tree_y]，這個由連接的那條邊的被經(jīng)過次數(shù)可以得出。

　　那么現(xiàn)在考慮三棵樹的情況，我們需要枚舉中間的樹，這樣左右兩棵樹肯定連接dis最大的點，中間的連接的則不確定，我們可以列出來整個答案的表達式，設(shè)左面的樹和中間的樹通過x,y點連通，中間的點和右面的樹通過u,v點連接，設(shè)三棵樹的size為size[1],size[2],size[3]，y與u點的距離為d[y][u]，那么答案就是size[1]*dis_[y]+size[2]*dis_[x]+size[1]*size[2]+size[3]*dis_[u]+size[2]*dis_[v]+size[1]*dis_[v]+size[3]*dis_[u]+size[1]*size[3]*(d[y][u]+2)

　　我們可以發(fā)現(xiàn)，這個中與y,u點有關(guān)的式子可以寫成a*dis_[y]+b*dis_[u]+c*d[u][v]的形式，其中a,b,c為常數(shù)，那么對于這個我們就可以用tree-dp搞出來，記錄點x的子樹中dis_[p]+(d[x][p]+1)*c的最大值，然后不斷的更新答案就可以了。

　　第二問比較簡單，我們可以貪心的來想，對于一棵樹，我們從葉子節(jié)點開始，因為葉子節(jié)點的度數(shù)為1，那么我們只需要判斷葉子節(jié)點的顏色，就可以判斷這個點和其父節(jié)點的邊是否可以刪掉。

　　反思：開始寫tree-dp維護中間樹的值的時候沒有考慮到一些特殊情況，比如連接的y,u點其中一點是另一點的祖先，還有開始覺得如果中間的樹選擇兩個點肯定不能是同一點，所以邊界就處理的不是特別好，但是可能會有某些點單獨構(gòu)成樹，這樣的話就必須連接同一個點。第二問還是比較容易寫的。

//By BLADEVIL #include <cstdio> #include <cstring> #include <algorithm> #define maxn 100010 #define LL long longusing namespace std;LL n,m,l; LL a[maxn],pre[maxn<<1],other[maxn<<1],last[maxn],col[maxn],rot[4],num[maxn<<1],flag[maxn]; LL dis_[maxn],dis[maxn],size[maxn],ans[maxn],ANS[4],max_a[maxn],max_b[maxn],cnt[maxn];void connect(LL x,LL y,LL z) {pre[++l]=last[x];last[x]=l;other[l]=y;num[l]=z; }void paint(LL x,LL fa,LL c) {col[x]=c;for (LL p=last[x];p;p=pre[p]) {if (other[p]==fa) continue;paint(other[p],x,c);} }void make_dis(LL x,LL fa) {dis[x]=0; size[x]=1;for (LL p=last[x];p;p=pre[p]) {if (other[p]==fa) continue;make_dis(other[p],x);dis[x]+=dis[other[p]]+size[other[p]];size[x]+=size[other[p]];} }void make_dis_(LL x,LL fa,LL s) {if (fa!=-1) dis_[x]=dis_[fa]-size[x]-dis[x]+s-size[x]+dis[x]; else dis_[x]=dis[x];for (LL p=last[x];p;p=pre[p]) {if (other[p]==fa) continue;make_dis_(other[p],x,s);} }void calc(LL x,LL fa,LL s) {for (LL p=last[x];p;p=pre[p]) {if (other[p]==fa) continue;ANS[col[x]]+=size[other[p]]*(s-size[other[p]]);calc(other[p],x,s);} }void dp(LL x,LL fa,LL a,LL b,LL c,LL &Ans) {max_a[x]=dis_[x]*a+c; max_b[x]=dis_[x]*b+c;for (LL p=last[x];p;p=pre[p]) {if (other[p]==fa) continue;dp(other[p],x,a,b,c,Ans);max_a[x]=max(max_a[x],max_a[other[p]]+c);max_b[x]=max(max_b[x],max_b[other[p]]+c);}LL aa=0,bb=0;//printf("%d %d\n",max_a[x],max_b[x]);for (LL p=last[x];p;p=pre[p]) {if (other[p]==fa) continue;Ans=max(Ans,max_a[x]+c+dis_[x]*b);Ans=max(Ans,max_b[x]+c+dis_[x]*a);}//printf("%d %d\n",x,Ans);for (LL p=last[x];p;p=pre[p]) {if (other[p]==fa) continue;if (max_a[other[p]]>max_a[aa]) aa=other[p];if (max_b[other[p]]>max_b[bb]) bb=other[p];}//printf("%d %d\n",x,Ans);for (LL p=last[x];p;p=pre[p]) {if (other[p]==fa) continue;if (other[p]!=aa) Ans=max(Ans,max_a[aa]+max_b[other[p]]+(c<<1));//printf("%d %d %d %d\n",Ans,max_a[aa],max_b[other[p]],c<<1);if (other[p]!=bb) Ans=max(Ans,max_b[bb]+max_a[other[p]]+(c<<1));}//printf("%d %d\n",aa,max_a[aa]);//printf("%d %d\n",x,Ans); }LL work(LL le,LL x,LL ri) {LL a=size[le],b=size[ri],c=size[le]*size[ri],ans=0;LL cur[4]; cur[1]=cur[2]=cur[3]=0;for (LL i=1;i<=n;i++) cur[col[i]]=max(cur[col[i]],dis_[i]);//printf("fuck %d %d\n",col[le],col[ri]);ans=cur[col[le]]*size[x]+a*size[x]+cur[col[ri]]*size[x]+size[x]*b+a*cur[col[ri]]+b*cur[col[le]];//printf("fuck\n");memset(max_a,0,sizeof max_a);memset(max_b,0,sizeof max_b);LL Ans=-1;dp(x,-1,a,b,c,Ans);Ans=max(Ans,c<<1);//printf("%d %d\n",ans,Ans);ans+=Ans;//printf("%d\n",ans);return ans; }void Work(LL x,LL fa) {for (LL p=last[x];p;p=pre[p]) {if (other[p]==fa) continue;Work(other[p],x);}//printf("%d %d %d\n",x,a[x],cnt[x]);if (a[x]^cnt[x]) {for (LL p=last[x];p;p=pre[p]) if (other[p]==fa) flag[num[p]]=1;cnt[fa]^=1;}; }int main() {freopen("lct.in","r",stdin); freopen("lct.out","w",stdout);scanf("%lld%lld\n",&n,&m);char c;for (LL i=1;i<=n;i++) scanf("%c",&c),a[i]=(c=='B')?1:0;for (LL i=1;i<=m;i++) {LL x,y;scanf("%lld%lld",&x,&y);connect(x,y,i); connect(y,x,i);}LL sum=0;for (LL i=1;i<=n;i++) if (!col[i]) paint(i,-1,++sum),rot[sum]=i;for (LL i=1;i<=3;i++) if (rot[i]) make_dis(rot[i],-1),make_dis_(rot[i],-1,size[rot[i]]);for (LL i=1;i<=3;i++) if (rot[i]) calc(rot[i],-1,size[rot[i]]);//for (LL i=1;i<=n;i++) printf("%d ",col[i]); printf("\n");//printf("%d %d %d\n",rot[1],rot[2],rot[3]);//for (LL i=1;i<=n;i++) printf("%d %d %d %d\n",i,dis[i],dis_[i],size[i]);//for (LL i=1;i<=3;i++) printf("%d ",ANS[i]); printf("\n");if (sum==2) {LL cur[3];cur[1]=cur[2]=0;for (LL i=1;i<=n;i++) cur[col[i]]=max(cur[col[i]],dis_[i]);LL Ans=ANS[1]+ANS[2]+cur[1]*size[rot[2]]+cur[2]*size[rot[1]]+size[rot[1]]*size[rot[2]];printf("%lld\n",Ans);//printf("%d %d\n",cur[1],cur[2]);//printf("%d %d\n",size[rot[1]],size[rot[2]]);//printf("%d %d\n",ANS[1],ANS[2]);} else {LL Ans=0;Ans=max(Ans,work(rot[2],rot[1],rot[3]));Ans=max(Ans,work(rot[1],rot[2],rot[3]));Ans=max(Ans,work(rot[1],rot[3],rot[2]));//printf("%d\n",Ans);Ans+=ANS[1]+ANS[2]+ANS[3];printf("%lld\n",Ans);}for (LL i=1;i<=n;i++) for (LL p=last[i];p;p=pre[p]) cnt[other[p]]++,cnt[i]++;//for (LL i=1;i<=n;i++) printf("%d\n",cnt[i]);//for (LL i=1;i<=n;i++) printf("%d\n",a[i]);for (LL i=1;i<=n;i++) cnt[i]/=2,cnt[i]%=2;for (LL i=1;i<=3;i++) Work(rot[i],-1);LL ans_=0;for (LL i=1;i<=m;i++) if (!flag[i]) ans_++;printf("%lld\n",ans_);for (LL i=1;i<=m;i++) if (!flag[i]) printf("%lld ",i); printf("\n");fclose(stdin); fclose(stdout);return 0; }

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/BLADEVIL/p/3625012.html

總結(jié)

以上是生活随笔為你收集整理的【HNOI】 lct tree-dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。