设$f[x][i][j]$表示以$x$为根的子树,与$x$连通部分有$i$个黑点,$j$个白点,不联通部分都是均衡的最小代价。若$i>1$,则视作$1$;若$j>2$,则视作$2$。

然后进行树形DP即可,转移的时候如果不要那棵子树,那么那棵子树的状态必须满足$!i||j<2$。

时间复杂度$O(n)$。

#include<cstdio>
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
const int N=300010;
const ll inf=1LL<<60;
int T,n,i,x,y,z,a[N],g[N],v[N<<1],w[N<<1],nxt[N<<1],ed;
ll f[N][2][3],h[2][3],ans;
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline void up(ll&a,ll b){if(a>b)a=b;}
inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}
inline int fix(int x){return x<2?x:2;}
void dfs(int x,int y){
rep(A,2)rep(B,3)f[x][A][B]=inf;
f[x][0][0]=0;
for(int i=g[x];i;i=nxt[i])if(v[i]!=y){
int u=v[i];
dfs(u,x);
rep(A,2)rep(B,3)h[A][B]=inf;
rep(A,2)rep(B,3)if(f[x][A][B]<inf)rep(C,2)rep(D,3)if(f[u][C][D]<inf){
up(h[A|C][fix(B+D)],f[x][A][B]+f[u][C][D]);
if(!C||D<2)up(h[A][B],f[x][A][B]+f[u][C][D]+w[i]);
}
rep(A,2)rep(B,3)f[x][A][B]=h[A][B];
}
rep(A,2)rep(B,3)h[A][B]=inf;
rep(A,2)rep(B,3)if(f[x][A][B]<inf)up(h[A|!a[x]][fix(B+(a[x]==1))],f[x][A][B]);
rep(A,2)rep(B,3)f[x][A][B]=h[A][B];
}
int main(){
for(read(T);T--;printf("%lld\n",ans)){
read(n);
for(ed=0,i=1;i<=n;i++)read(a[i]),g[i]=0;
for(i=1;i<n;i++)read(x),read(y),read(z),add(x,y,z),add(y,x,z);
dfs(1,0);
ans=inf;
rep(A,2)rep(B,3)if(!A||B<2)up(ans,h[A][B]);
}
return 0;
}

  

最新文章

  1. 并联机构逆运动学用MapleSim符号来解决
  2. typedef和#define的用法与区别
  3. 转-JS子窗口创建父窗口操作父窗口
  4. LCA(Tarjan)
  5. 优雅降级&amp;渐进增强
  6. Xmind 快捷键
  7. javascript权威指南(2)
  8. 【mp3】洗脑循环了!龙珠超 自在极意功 【究极の圣戦】串田アキラ 背景纯音乐
  9. DB2常用命令2
  10. JavaScript(四)
  11. Ubuntu16.04修改IP及时生效
  12. C++ vector动态数组
  13. [MySQL] INFORMATION_SCHEMA 数据库包含所有表的字段
  14. Jmeter入门(压力测试)
  15. cmd运行java程序---路径容易出错的问题
  16. Unity触发器有时失效的原因
  17. 解决SecureCRT/Xshell无法以root用户连接Ubuntu
  18. MVC5使用EF6 Code First--创建EF数据模型(一)
  19. requires the FLAG_ACTIVITY_NEW_TASK flag
  20. Vim 使用入门快捷键

热门文章

  1. 关于安装Ubuntu后触摸板无法使用的解决方案
  2. 三、jQuery--jQuery基础--jQuery基础课程--第6章 jQuery 事件与应用
  3. 数据结构和算法 c#&ndash; 1.单项链表
  4. Java集合源码学习(五)几种常用集合类的比较
  5. 【转】JQuery插件ajaxFileUpload 异步上传文件(PHP版)
  6. Notice: Only variable references should be returned by reference(PHP版本兼容性问题)
  7. Python无类再理解--metaclass,type
  8. 【openGL】画五角星
  9. Centos6.5里安装Erlang 并安装riak
  10. PHP实现上一篇、下一篇