poj 1741 ：男人八题23333
poj 2114：限制条件变成==k，该怎么弄怎么弄
省队互测题
BZOJ 1267 ←还没交
关于合并答案：
现在我们在点p，
p有各种孩子：b1,b2,b3,...,bn
首先可以得到他们的答案ans1...ansn
然后考虑经过p点的情形。
1）如果是要在限制Y下最大化XXXX（要满足可加性）
从一个子树出发，dfs出deepX情况下的最优解que[deep]
考虑这个最优解和前一颗线段树满足限制Y下的区间中的最优解的合并是否最优。
然后把这颗子树丢进线段树tree[deep]（deep为关键字）
但是还有个单调性的做法：
当限制范围是L<=DIST<=R时
最大化tree[X]+que[Y] | L<=X+Y<=R,X,Y>=0
显然，如果X固定了，问题就变成求出que[L-X]到que[R-X]之间的最大值。
X单增，L-X,R-X也是单增，用单调队列维护就可以了。
nlogn->n daze~啦啦啦啦啦比线段树好些多了23333
（某题解，差评！）
2）如果是要在限制条件Y下统计XXXX的个数
把条件转换成最好处理的，
利用单调性，类似统计逆序数的
统计一个子树下的答案，和所有子树下的答案……
然后该咋搞咋搞……
// 这只是一个简单的模板，在// ???填充代码……
#include <cstdio>
#include <cstdlib>
const int maxn = 100010;
const int maxm = 200010;
int n,l,r,mid;
struct node{
int u,v,c;
bool flag;
node*next,*inv;
}E[maxm];int size = 0;
node * V[maxn];
int gravity[maxn];
int csize = 0;
int sum[maxn],balance[maxn];
bool inba[maxn];
int nsize = 0;
void callbalance(int root){
nsize++;
inba[root] = true;
sum[root] = 1;
for (node * it = V[root];it!=NULL; it = it->next){
if (!t->flag){
it->flag = it->inv->flag = true;
callbalance(it->v);
it->flag = it->inv->flag = false;
sum[root]+=sum[it->v];
balance[root] = (sum[it->v],balance[root]);
}
}
}
void callgravity(int root){
csize = 0;
memset(inba,0,sizeof(inba));
node * p = V[root];
callbalance(root);
for(int i=1; i <= n; i++){
if (inba[i]) balance[i] = max(nsize - sum[i] , balance[i]);
}
int mn = balance[root],int index = root;
for(int i=1; i <= n; i++){
if (inba[i]){ mn = balance[i]; index = i; }
}
gravity[root] = index;
for (node * it = V[index];it!=NULL; it = it->next){
if (!t->flag){
it->flag = it->inv->flag = true;
callbalance(it->v);
it->flag = it->inv->flag = false;
}
}
}
int calc(int x){
node * q = V[gravity[x]];
int ans = 0;
int rst = 0;
for (node * it = q;it!=NULL;it = it->next){
if (!t->flag){
it->flag = true;
it->inv->flag = true;
ans = max(ans,calc(it->v));
it->flag = false;
it->inv->flag = false;
}
}
// ???在这里合并。
return max(ans,rst);
};
node* insert(int u,int v,int c,int g = 0,node *inv = NULL){
node * p = &E[size++];
p->u = u;p->v = v;p->c = c;p->g = g;p -> inv = inv?inv:insert(v,u,c,g,p);
p->next = V[u];V[u]=p;
return p;
}
int main(){
scanf("%d%d%d",&n,&l,&r);
for (int i = 0;i < n-1;i++)
{
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
insert(u,v,c);
};
callgravity(1);
}
