题解：
好题！！
这题似乎能上我代码长度记录的前五？
调试时间长度应该也能上前五QAQ
首先题目要求的明显就是最小割，当然在整个森林上求Q次最小割肯定是会GG的，所以我们需要一个能快速求最小割的算法——最小割树。
最小割树，也叫分治最小割，就是通过预处理把原本的图缩成一颗树，树上两个节点路径上的最小边权就是它们的最小割，这个用树上倍增可以随便维护。
大概思想就是先求一次最小割，把划分出的S和T两个点集继续求最小割，向下分治然后连边缩点。
这题先对每个州预处理最小割树，州和州之间用KD树求出距离最近的点，然后查询的时候用树上倍增跳。
分别写出来就好了qwq
所以这就是道码农题，码码码码码码
有必要说一下时间复杂度是O（玄学），这个时间复杂度严格来说是过不了的，但是数据随机，每个州和大的森林联通块的期望大小不大，所以不知道为什么就过了。。。
PS：我没写KD树，写了个排序剪枝，也是玄学就过了。。。
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#define inf 2147483647
#define eps 1e-9
using namespace std;
typedef long long ll;
struct node{
int x,y,id;
friend bool operator <(node a,node b){
if(a.x!=b.x)return a.x<b.x;
if(a.y!=b.y)return a.y<b.y;
return a.id<b.id;
}
}p[],pp[];
int N,n,m,q,u,v,w,ta,tb,qa,qb,cnt=,bcc=,num[],fr[],pts[],blg[];
bool used[];
namespace capitals{
struct edge{
int v,w,next;
}a[];
int tot=,head[],dep[],fa[][],minn[][];
void add(int u,int v,int w){
a[++tot].v=v;
a[tot].w=w;
a[tot].next=head[u];
head[u]=tot;
}
void dfs(int u,int ff,int dpt,int d){
blg[u]=bcc;
dep[u]=dpt;
fa[u][]=ff;
minn[u][]=d;
for(int i=;i<=;i++){
fa[u][i]=fa[fa[u][i-]][i-];
minn[u][i]=min(minn[u][i-],minn[fa[u][i-]][i-]);
}
for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){
int v=a[tmp].v;
if(v!=ff){
dfs(v,u,dpt+,a[tmp].w);
}
}
}
int query(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int ret=inf;
for(int i=;i>=;i--){
if(dep[fa[u][i]]>=dep[v]){
ret=min(ret,minn[u][i]);
u=fa[u][i];
}
}
if(u==v)return ret;
for(int i=;i>=;i--){
if(fa[u][i]!=fa[v][i]){
ret=min(ret,min(minn[u][i],minn[v][i]));
u=fa[u][i],v=fa[v][i];
}
}
return min(ret,min(minn[u][],minn[v][]));
}
}
namespace dinic{
struct edge{
int v,w,next;
}a[];
int n,m,vs,vt,tot=,dep[],s[],flw[],nmd[],head[];
queue<int>q;
void add(int u,int v,int w){
a[++tot].v=v;
a[tot].w=w;
a[tot].next=head[u];
head[u]=tot;
}
void clr(){
//memset(head,-1,sizeof(head));
for(int i=;i<=n;i++)head[i]=-;
tot=;
}
bool bfs(){
for(int i=;i<=n;i++)dep[i]=;
while(!q.empty())q.pop();
q.push(vs);
dep[vs]=;
while(!q.empty()){
int u=q.front();
q.pop();
for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){
int v=a[tmp].v;
if(!dep[v]&&a[tmp].w){
dep[v]=dep[u]+;
if(v==vt)return true;
q.push(v);
}
}
}
return false;
}
int dfs(int u,int num){
if(u==vt||!num)return num;
int ans=;
for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){
int v=a[tmp].v;
if(dep[v]==dep[u]+&&a[tmp].w){
int f=dfs(v,min(num,a[tmp].w));
if(f){
a[tmp].w-=f;
a[tmp^].w+=f;
ans+=f;
num-=f;
if(!num)break;
}
}
}
if(!ans)dep[u]=-;
return ans;
}
void build_mincost(int l,int r){
if(r<=l)return;
int dnc=,ls=l,rs=r;
vs=nmd[l],vt=nmd[r];
for(int i=;i<=tot+;i++)a[i].w=flw[i/];
while(bfs())dnc+=dfs(vs,inf);
for(int i=l;i<=r;i++){
if(dep[nmd[i]])s[ls++]=nmd[i];
else s[rs--]=nmd[i];
}
for(int i=l;i<=r;i++)nmd[i]=s[i];
capitals::add(vs+cnt,vt+cnt,dnc);
capitals::add(vt+cnt,vs+cnt,dnc);
//printf("Added %d->%d Flow=%d\n",vs+cnt,vt+cnt,dnc);
build_mincost(l,ls-);
build_mincost(rs+,r);
}
}
int dis(node a,node b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void solve(int k){
int ans=inf,now=;
for(int i=k+;i<=N;i++){
if((pp[i].x-pp[k].x)*(pp[i].x-pp[k].x)>ans)break;
int ds=dis(pp[i],pp[k]);
if(ds<ans){
ans=ds;
now=i;
}else if(ds==ans&&pp[i].id<pp[now].id)now=i;
}
for(int i=k-;i;i--){
if((pp[i].x-pp[k].x)*(pp[i].x-pp[k].x)>ans)break;
int ds=dis(pp[i],pp[k]);
if(ds<ans){
ans=ds;
now=i;
}else if(ds==ans&&pp[i].id<pp[now].id)now=i;;
}
fr[pp[k].id]=pp[now].id;
}
int main(){
memset(capitals::head,-,sizeof(capitals::head));
scanf("%d",&N);
for(int i=;i<=N;i++){
scanf("%d%d%d%d%d",&p[i].x,&p[i].y,&num[i],&n,&m);
p[i].id=i;
pp[i]=p[i];
pts[i]=cnt+;
dinic::n=n;
dinic::m=m;
dinic::clr();
for(int j=;j<=n;j++)dinic::nmd[j]=j;
for(int j=;j<=m;j++){
scanf("%d%d%d",&u,&v,&w);
dinic::add(u,v,w);
dinic::add(v,u,w);
dinic::flw[j]=w;
}
dinic::build_mincost(,n);
cnt+=n;
}
sort(pp+,pp+N+);
for(int i=;i<=N;i++)solve(i);
for(int i=;i<=N;i++){
if(used[i])continue;
if(i==fr[fr[i]]){
used[fr[i]]=true;
capitals::add(pts[i],pts[fr[i]],num[i]+num[fr[i]]);
capitals::add(pts[fr[i]],pts[i],num[i]+num[fr[i]]);
//printf("Added %d->%d Flow=%d\n",pts[fr[i]],pts[i],num[i]+num[fr[i]]);
}else{
capitals::add(pts[i],pts[fr[i]],num[i]);
capitals::add(pts[fr[i]],pts[i],num[i]);
//printf("Added %d->%d Flow=%d\n",pts[fr[i]],pts[i],num[i]);
}
}
for(int i=;i<=N;i++){
if(!blg[pts[i]]){
bcc++;
capitals::dfs(pts[i],,,inf);
}
}
scanf("%d",&q);
for(int i=;i<=q;i++){
scanf("%d%d%d%d",&ta,&tb,&qa,&qb);
qa=pts[ta]+qa-;
qb=pts[tb]+qb-;
if(blg[qa]!=blg[qb])puts("");
else printf("%d\n",capitals::query(qa,qb));
}
return ;
}