寒假集训1-2 variable

有 n 个变量 w[1]~w[n],每个变量可以取 W 或-W。 有 p 个式子,形如 Hi=ai|w[xi]-w[yi]|+bi|w[yi]-w[zi]|+ci|w[zi]-w[xi]| +di(w[xi]-w[yi])+ei(w[yi]-w[zi])+fi(w[zi]-w[xi])。 有 q 个条件,形如 w[x]<=w[y]或 w[x]=w[y]或 w[x]<w[y]。 最小化 sigma(wi)+sigma(Hi)。

HDU5029 Relief grain

题意

有n个村庄,连成一棵树。

有m次操作,每次形如u,v,wu,v,w,表示给从u到v的所有村庄颁发一个类型为w的证书,求每个村庄得到哪类证书的个数最多。若有多个输出类型最小值,若没有证书输出0

n,m,w105n,m,w\le 10^5

HDU6162 Ch's gift

给定一棵树,已知每个点点权wiw_i,每次给定s,t,a,bs,t,a,b,求从s到t的路径上满足aa\le点权b\le b的点的点权和。

点数,询问数105\le 10^5,多组数据,wi,a,b109w_i,a,b\le 10^9

|