lyzlyz?lyzlyz!

听说这是JSOIDay6（为什么江苏有这么多省选）

膜了贵省的题目，感到不明觉厉。

T1

这是一道人类智慧题。（其实是窝想错了）

考试时不断YY费用流的模型。（其实是被Gold_7误导了）

然而这是一道区间dp。

把每个敌人抽象为左端点为ai，右端点为bi，高度为ci的线段。

对于区间[l,r]，找到其中最高的线段，枚举上面的点，然后用一条直线切断它以及它下方可以切断的点，那么就阔以转移辣！

T2

这是一道难题。（其实是因为gonens不会做）

那么就介绍一下60分蒜法：枚举根，dfs，然后在线段树上修改和询问就阔以辣！

（然而窝忘记开longlong了）

T3

这是一道码农题。（其实是窝写得臭）

考试的时候发现在线是用来搞笑的。

后来正解说明在线确实是用来搞笑的。

首先从大到小枚举边，并查集维护连通性，如果不在同一个集合里就直接加上去，否则找到环上最大的边，删去。

接着用可持久化线段树维护一下选择的边。

最后对于区间[l,r]就是在编号为l的线段树上询问[l,r]。

（然而其中的离散实在是太蛋疼了）

[Codes]

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=1010;
int cas,n,i,j,k,p,cnt;
int a[M],b[M],c[M],g[M],A[M],f[M][M];
int main(){
		memset(f,0,sizeof f);
		scanf("%d",&n);
		cnt=0;
		for (i=1;i<=n;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]),A[++cnt]=a[i],A[++cnt]=b[i];
		sort(A+1,A+cnt+1);
		cnt=unique(A+1,A+cnt+1)-A-1;
		for (i=1;i<=n;i++)a[i]=lower_bound(A+1,A+cnt+1,a[i])-A,b[i]=lower_bound(A+1,A+cnt+1,b[i])-A;
		for (p=1;p<cnt;p++)
			for (i=1;i<=cnt-p;i++){
				memset(g,0,sizeof g);
				int j=i+p,mx=0;
				f[i][j]=1000000007;
				for (k=1;k<=n;k++)
					if (a[k]>=i&&b[k]<=j&&c[k]>mx)mx=c[k];
				if (!mx){f[i][j]=0;continue;}
				for (k=1;k<=n;k++)
					if (a[k]>=i&&b[k]<=j&&c[k]==mx)g[b[k]+1]--,g[a[k]]++;
				for (k=i+1;k<=j;k++)g[k]+=g[k-1];
				for (k=i;k<=j;k++)
					if (g[k]>0)f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+mx);
			}
		printf("%d\n",f[1][cnt]);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1000010;
const int M=5010;
long long ans1;
int n,i,x,y,ch,edgenum,ans2;
int head[M],vet[M],next[M],len[M],flag[M];
int tree[maxn*4];
void addedge(int x,int y,int ch){
	vet[++edgenum]=y;
	next[edgenum]=head[x];
	head[x]=edgenum;
	len[edgenum]=ch;
}
int query(int x,int l,int r,int p){
	if (l==r)return l;
	int mid=l+r>>1;
	if (tree[p<<1]>=x)return query(x,l,mid,p<<1);
		else return query(x-tree[p<<1],mid+1,r,p<<1|1);
}
void update(int x,int l,int r,int p,int t){
	tree[p]+=t;
	if (l==r)return;
	int mid=l+r>>1;
	if (x<=mid)update(x,l,mid,p<<1,t);
		else update(x,mid+1,r,p<<1|1,t);
}
void dfs(int u,int dep){
	int e,v;
	flag[u]=1;
	if (dep&1)ans1+=query(dep/2+1,1,maxn,1),ans2++;
	for (e=head[u];e;e=next[e]){
		v=vet[e];
		if (flag[v])continue;
		update(len[e],1,maxn,1,1);
		dfs(v,dep+1);
		update(len[e],1,maxn,1,-1);
	}
}
int main(){
	scanf("%d",&n);
	for (i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&ch);
		addedge(x,y,ch);
		addedge(y,x,ch);
	}
	for (i=1;i<=n;i++){
		memset(flag,0,sizeof flag);
		dfs(i,0);
	}
	printf("%.7lf\n",(double)ans1/ans2);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=200010;
int n,m,i,j,sum,q,opt,x,y,ans,edgenum,cnt,mx,tot;
int A[M],B[M],b[M],root[M],f[M],id[M],fi[M];
int head[1010],edg[1010],vet[M],next[M],len[M],isok[M],data[M];
struct shit{int x,y,w;}a[M];
struct node{int l,r,w;}tree[M*40];
bool cmp(shit x,shit y){return x.w>y.w;}
void addedge(int x,int y,int ch,int w){
	vet[++edgenum]=y;
	next[edgenum]=head[x];
	head[x]=edgenum;
	len[edgenum]=ch;
	data[edgenum]=w;
}
int dfs(int u,int pre,int st){
	int e,v;
	if (u==st&&pre!=-1)return 1;
	for (e=head[u];e;e=next[e]){
			v=vet[e];
			if (e==(pre^1))continue;
			if (dfs(v,e,st)){
				if (len[e]>len[mx])mx=e;
				return 1;
			}
		}
	return 0;
}
int search(int x){
	if (f[x]!=x)f[x]=search(f[x]);
	return f[x];
}
void update(int x,int l,int r,int &p,int t){
	tree[++cnt]=tree[p],p=cnt,tree[p].w+=t;
	if (l==r)return;
	int mid=l+r>>1;
	if (x<=mid)update(x,l,mid,tree[p].l,t);
		else update(x,mid+1,r,tree[p].r,t);
}
int query(int x,int y,int l,int r,int p){
	if (x>y)return 0;
	if (x==l&&y==r)return tree[p].w;
	int mid=l+r>>1;
	if (y<=mid)return query(x,y,l,mid,tree[p].l);
		else if (x>mid)return query(x,y,mid+1,r,tree[p].r);
			else return query(x,mid,l,mid,tree[p].l)+query(mid+1,y,mid+1,r,tree[p].r);
}
int main(){
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
	int mm=0;
	for (i=1;i<=m;i++)if (a[i].x!=a[i].y)a[++mm]=a[i];
	m=mm;
	sort(a+1,a+m+1,cmp);
	for (i=1;i<=m;i++)A[i]=a[m-i+1].w;
	sum=unique(A+1,A+m+1)-A-1;
	for (i=1;i<=m;i++)id[i]=lower_bound(A+1,A+sum+1,a[i].w)-A;
	for (i=1;i<=m;i++)id[i]=sum-id[i]+1;
	for (i=1;i<=n;i++)f[i]=i;
	for (i=1;i<=m;i++){
		edgenum=1;
		memset(head,0,sizeof head);
		for (j=1;j<=edg[0];j++)addedge(a[edg[j]].x,a[edg[j]].y,a[edg[j]].w,edg[j]),addedge(a[edg[j]].y,a[edg[j]].x,a[edg[j]].w,edg[j]);
		root[i]=root[i-1];
		fi[id[i]]=i;
		edg[++edg[0]]=i;
		addedge(a[i].x,a[i].y,a[i].w,i);
		addedge(a[i].y,a[i].x,a[i].w,i);
		update(id[i],1,sum,root[i],a[i].w);
		int p=search(a[i].x),q=search(a[i].y);
		if (p!=q){
			f[p]=q;
			continue;
		}
		mx=0;
		dfs(a[i].x,-1,a[i].x);
		mx=data[mx];
		update(id[mx],1,sum,root[i],-a[mx].w);
		int mm=0;
		for (j=1;j<=edg[0];j++)if (edg[j]!=mx)edg[++mm]=edg[j];
		edg[0]=mm;
	}
	scanf("%d%d",&q,&opt);
	while (q--){
		scanf("%d%d",&x,&y);
		int l=ans*opt+x,r=l+y,pre=r;
		if (l>A[sum]){puts("0");ans=0;continue;}
		l=lower_bound(A+1,A+sum+1,l)-A;
		r=upper_bound(A+1,A+sum+1,r)-A-1;
		r=sum-r+1,l=sum-l+1;
		ans=query(r,l,1,sum,root[fi[l]]);
		printf("%d\n",ans);
	}
}