编织幻梦

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);

}