建立自己的公司网站,建设网站的基本知识,wordpress 首页缓存,游戏推广员【题目描述】给定2-3颗树#xff0c;每个边的边权为1#xff0c;解决以下独立的问题。 现在通过连接若干遍使得图为连通图#xff0c;并且Σdis(x,y)最大#xff0c;x#xff0c;y只算一次。 每个点为黑点或者白点#xff0c;现在需要删除一些边#xff0c;使得图中的黑… 【题目描述】给定2-3颗树每个边的边权为1解决以下独立的问题。 现在通过连接若干遍使得图为连通图并且Σdis(x,y)最大xy只算一次。 每个点为黑点或者白点现在需要删除一些边使得图中的黑点度数为奇数白点为偶数要求删除的边最多。 【数据范围】 100% n10^5 首先我们来解决第一问因为每加一条边就可能使得若干点到其他点的距离变小那么我们需要加尽量少的边来使得图连通。 设dis_[x]为x在x所在子树中x到其他所有点的距离这个我们可以通过设dis[x]表示x到x子树中所有点的距离和来由父节点转移得到。 那么答案可以分为两部分分别为树中的点对距离和跨树的点对距离前一个问题比较容易可以通过dis_[x]或者计算每条边被经过的次数来求出。 那么对于两颗树的情况我们就需要连接这两棵树中dis值最大的两个点假设为xy。这样答案就是 dis[x]*size[tree_y]dis[y]*size[tree_x]size[tree_x]*size[tree_y]这个由连接的那条边的被经过次数可以得出。 那么现在考虑三棵树的情况我们需要枚举中间的树这样左右两棵树肯定连接dis最大的点中间的连接的则不确定我们可以列出来整个答案的表达式设左面的树和中间的树通过x,y点连通中间的点和右面的树通过u,v点连接设三棵树的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) 我们可以发现这个中与y,u点有关的式子可以写成a*dis_[y]b*dis_[u]c*d[u][v]的形式其中a,b,c为常数那么对于这个我们就可以用tree-dp搞出来记录点x的子树中dis_[p](d[x][p]1)*c的最大值然后不断的更新答案就可以了。 第二问比较简单我们可以贪心的来想对于一棵树我们从叶子节点开始因为叶子节点的度数为1那么我们只需要判断叶子节点的颜色就可以判断这个点和其父节点的边是否可以删掉。 反思开始写tree-dp维护中间树的值的时候没有考虑到一些特殊情况比如连接的y,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[maxn1],other[maxn1],last[maxn],col[maxn],rot[4],num[maxn1],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 plast[x];p;ppre[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 plast[x];p;ppre[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 plast[x];p;ppre[p]) {if (other[p]fa) continue;make_dis_(other[p],x,s);}
}void calc(LL x,LL fa,LL s) {for (LL plast[x];p;ppre[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]*ac; max_b[x]dis_[x]*bc;for (LL plast[x];p;ppre[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 aa0,bb0;//printf(%d %d\n,max_a[x],max_b[x]);for (LL plast[x];p;ppre[p]) {if (other[p]fa) continue;Ansmax(Ans,max_a[x]cdis_[x]*b);Ansmax(Ans,max_b[x]cdis_[x]*a);}//printf(%d %d\n,x,Ans);for (LL plast[x];p;ppre[p]) {if (other[p]fa) continue;if (max_a[other[p]]max_a[aa]) aaother[p];if (max_b[other[p]]max_b[bb]) bbother[p];}//printf(%d %d\n,x,Ans);for (LL plast[x];p;ppre[p]) {if (other[p]fa) continue;if (other[p]!aa) Ansmax(Ans,max_a[aa]max_b[other[p]](c1));//printf(%d %d %d %d\n,Ans,max_a[aa],max_b[other[p]],c1);if (other[p]!bb) Ansmax(Ans,max_b[bb]max_a[other[p]](c1));}//printf(%d %d\n,aa,max_a[aa]);//printf(%d %d\n,x,Ans);
}LL work(LL le,LL x,LL ri) {LL asize[le],bsize[ri],csize[le]*size[ri],ans0;LL cur[4]; cur[1]cur[2]cur[3]0;for (LL i1;in;i) cur[col[i]]max(cur[col[i]],dis_[i]);//printf(fuck %d %d\n,col[le],col[ri]);anscur[col[le]]*size[x]a*size[x]cur[col[ri]]*size[x]size[x]*ba*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);Ansmax(Ans,c1);//printf(%d %d\n,ans,Ans);ansAns;//printf(%d\n,ans);return ans;
}void Work(LL x,LL fa) {for (LL plast[x];p;ppre[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 plast[x];p;ppre[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 i1;in;i) scanf(%c,c),a[i](cB)?1:0;for (LL i1;im;i) {LL x,y;scanf(%lld%lld,x,y);connect(x,y,i); connect(y,x,i);}LL sum0;for (LL i1;in;i) if (!col[i]) paint(i,-1,sum),rot[sum]i;for (LL i1;i3;i) if (rot[i]) make_dis(rot[i],-1),make_dis_(rot[i],-1,size[rot[i]]);for (LL i1;i3;i) if (rot[i]) calc(rot[i],-1,size[rot[i]]);//for (LL i1;in;i) printf(%d ,col[i]); printf(\n);//printf(%d %d %d\n,rot[1],rot[2],rot[3]);//for (LL i1;in;i) printf(%d %d %d %d\n,i,dis[i],dis_[i],size[i]);//for (LL i1;i3;i) printf(%d ,ANS[i]); printf(\n);if (sum2) {LL cur[3];cur[1]cur[2]0;for (LL i1;in;i) cur[col[i]]max(cur[col[i]],dis_[i]);LL AnsANS[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 Ans0;Ansmax(Ans,work(rot[2],rot[1],rot[3]));Ansmax(Ans,work(rot[1],rot[2],rot[3]));Ansmax(Ans,work(rot[1],rot[3],rot[2]));//printf(%d\n,Ans);AnsANS[1]ANS[2]ANS[3];printf(%lld\n,Ans);}for (LL i1;in;i) for (LL plast[i];p;ppre[p]) cnt[other[p]],cnt[i];//for (LL i1;in;i) printf(%d\n,cnt[i]);//for (LL i1;in;i) printf(%d\n,a[i]);for (LL i1;in;i) cnt[i]/2,cnt[i]%2;for (LL i1;i3;i) Work(rot[i],-1);LL ans_0;for (LL i1;im;i) if (!flag[i]) ans_;printf(%lld\n,ans_);for (LL i1;im;i) if (!flag[i]) printf(%lld ,i); printf(\n);fclose(stdin); fclose(stdout);return 0;
} 转载于:https://www.cnblogs.com/BLADEVIL/p/3625012.html
