题意

ξ 得到了一棵圣诞树，他需要在上面挂满礼物。
ξ 会事先进行m个操作，每次在一条链（u[i],v[i]）上的每个点上挂上a[i]个种类为b[i]的礼物。
一个点的k-美观度这样计算：把这个点上的所有种类的礼物按照个数从小到大排序，如果个数一样就按照种类从小到大排。
它的k-美观度就是排好序后前k种礼物种类的xor值（如果礼物种类不足k种，就把这个点上所有礼物的种类xor起来）。
接下来给Q个询问，给定w[i],k[i]，求点w[i]的k[i]-美观度。

前言

这题真是做的我**了。。
想了一个早上，然后写了两个错误的想法。。
然后一个上午就成功过去了。。
什么都没做
下午又调了一个下午。。
一天就没了QAQ

题解

容易想到，这种东西可以树上差分
两个端点处挂上a[i]个b[i]，在端点lca及lca的父亲处挂上-a[i]个b[i]，询问子树的k-美观度
子树可以想到dfs序
因为dfs序的特殊性，所以所有区间都是包含或相离的
然后就可以分治了啊。。
考虑扩过中界线的
那么肯定是可以单调的啊
加入新的点，维护信息就用一个splay就可以了

要注意的是，在分治结构中，要注意所有全局变量的初始化，我就因为有一个没搞好调了很久QAQ

CODE:

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> PI;
const int N=100005;
int n,m;
struct qq {int x,y,last; }e[N*2];int num,last[N];
void init (int x,int y)
{num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;
}
int fa[N][21];
int dep[N];
int L[N],R[N],cnt;
void dfs (int x)
{L[x]=++cnt;for (int u=1;u<=20;u++) fa[x][u]=fa[fa[x][u-1]][u-1];for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (y==fa[x][0]) continue;dep[y]=dep[x]+1;fa[y][0]=x;dfs(y);}R[x]=cnt;
}
int get (int x,int y)
{if (dep[x]>dep[y]) swap(x,y);for (int u=20;u>=0;u--)if (dep[fa[y][u]]>=dep[x])y=fa[y][u];if (x==y) return x;
//  printf("lalal:%d %d\n",x,y);for (int u=20;u>=0;u--)if (fa[x][u]!=fa[y][u]){
   x=fa[x][u];y=fa[y][u];}return fa[x][0];
}
vector<PI> s[N];//各种修改操作 
int Q;
int ans[N];
struct qt{
   int l,r,k,id;}q[N];
struct qr {int f,son[2],c;//父亲 儿子 有多少个点 int a,b;//次数和值int ans;//子树的答案 }tr[N*3];
bool operator < (const qr &x,const qr &y){
   return x.a==y.a?x.b<y.b:x.a<y.a;}
int root;
int vis[N];//这个种类是什么点 
queue<int> o;//我们用了哪些种类
void update (int x)
{int s1=tr[x].son[0],s2=tr[x].son[1];tr[x].c=tr[s1].c+tr[s2].c+1;tr[x].ans=(tr[s1].ans^tr[s2].ans^tr[x].b);return ;
}
void add (int a,int b,int fa)//新建一个节点 
{num++;vis[b]=num;tr[num].f=fa;tr[num].son[0]=tr[num].son[1]=0;tr[num].a=a;tr[num].b=b;tr[num].c=1;tr[num].ans=b;if (tr[num]<tr[fa]) tr[fa].son[0]=num;else tr[fa].son[1]=num;
}
int find (int a,int b)//反正肯定不存在，随便找一个就好了。。 
{int x=root;qr lalal;lalal.a=a;lalal.b=b;while (true){if (lalal<tr[x]){if (tr[x].son[0]==0) break;x=tr[x].son[0];}else{if (tr[x].son[1]==0) break;x=tr[x].son[1];}}return x;
}
void rotate (int x)
{int y=tr[x].f,z=tr[y].f,r,R;int w=(tr[y].son[0]==x);r=tr[x].son[w];R=y;tr[R].son[1-w]=r;if (r!=0) tr[r].f=R;r=x;R=z;if (tr[R].son[0]==y) tr[R].son[0]=x;else tr[R].son[1]=x;tr[r].f=R;r=y;R=x;tr[R].son[w]=r;if (r!=0) tr[r].f=R;update(y);update(x);
}
void splay (int x,int rt)
{update(x);while (tr[x].f!=rt){int y=tr[x].f,z=tr[y].f;if (z==rt) rotate(x);else{if ((tr[y].son[0]==x)==(tr[z].son[0]==y)) rotate(y);else rotate(x);rotate(x);}}if (rt==0) root=x;
}
void ins (int a,int b)//加入一个点   出现次数是a，种族是b  保证不存在 
{if (root==0)    {add(a,b,0);root=num;return ;}int x=find(a,b);add(a,b,x);
//  printf("TYB:%d %d %d\n",a,b,x);splay(x,0);
}
void del (int x)//删除这个点 
{splay(x,0);if (tr[x].son[0]==0&&tr[x].son[1]==0)   {num=root=0;return ;}if (tr[x].son[0]==0&&tr[x].son[1]!=0)   {root=tr[x].son[1];tr[root].f=0;return ;}if (tr[x].son[0]!=0&&tr[x].son[1]==0)   {root=tr[x].son[0];tr[root].f=0;return ;}else{int p=tr[x].son[0];while (tr[p].son[1]!=0) p=tr[p].son[1];splay(p,x);root=p;tr[root].f=0;int r=tr[x].son[1],R=root;tr[R].son[1]=r;tr[r].f=R;update(R);}
}
void print (int now)
{if (now==0) return ;printf("%d:%d %d ans:%d s1:%d s2:%d\n",now,tr[now].a,tr[now].b,tr[now].ans,tr[now].son[0],tr[now].son[1]);print(tr[now].son[0]);print(tr[now].son[1]);
}
void Ins (int x)//把这个点的信息加入进来 
{
//  printf("YES:%d\n",x);int tot=s[x].size();for (int u=0;u<tot;u++){int xx=s[x][u].second;//加入这个种类//printf("%d %d\n",s[x][u].first,xx);if (vis[xx]==0) {o.push(xx);ins(s[x][u].first,xx);}else{int now=vis[xx];del(now);if (tr[now].a+s[x][u].first==0)//如果是 vis[xx]=0;else ins(tr[now].a+s[x][u].first,tr[now].b);}//  printf("O:%d\n",tr[root].ans);//print(root);}/*system("pause");printf("NO\n");*/}
int get (int k)//排名第k的节点是什么 
{int x=root;while (true){int s1=tr[x].son[0],s2=tr[x].son[1];if (k<=tr[s1].c) x=s1;else if (k>tr[s1].c+1) x=s2,k=k-tr[s1].c-1;else break;}return x;
}
int find (int k)//寻找前k个 
{if (tr[root].c<=k)  return tr[root].ans;int x=get(k+1);splay(x,0);return tr[tr[x].son[0]].ans;
}
queue<qt> A,B,C;
bool cmpq(qt x,qt y){
   return x.l==y.l?x.r<y.r:x.l>y.l;}
void solve (int l,int r,int L,int R)//处理到的区间     要处理的询问 
{if (L>R) return ;// printf("TYB:%d %d %d %d\n",l,r,L,R);if (l==r){Ins(l);//  printf("YES\n");for (int u=L;u<=R;u++)  ans[q[u].id]=find(q[u].k);while (!o.empty())  {
   int xx=o.front();vis[xx]=0;o.pop();}   root=num=0;return ;}int mid=(l+r)>>1;
//  printf("l:%d r:%d mid:%d %d %d\n",l,r,mid,L,R);for (int u=L;u<=R;u++){if (q[u].r<mid) {//  printf("A;%d %d\n",q[u].l,q[u].r);A.push(q[u]);}else if (q[u].l>mid) {//  printf("B:%d %d\n",q[u].l,q[u].r);B.push(q[u]);}else C.push(q[u]);}//C这次要处理的，A递归到左边的，B递归到右边的 int g=L,h=L;int now=L; while (!A.empty())  {
   q[now]=A.front();A.pop();now++;}h=now;while (!B.empty())  {
   q[now]=B.front();B.pop();now++;}g=now;while (!C.empty())  {
   q[now]=C.front();C.pop();now++;}solve(l,mid-1,L,h-1);solve(mid+1,r,h,g-1);//那么now到现在的就是我们要处理的了if (g>R) return ;sort(q+g,q+1+R,cmpq); int ll=mid,rr=mid;
/*printf("OZY:l:%d r:%d g:%d R:%d\n",l,r,g,R);for (int u=g;u<=R;u++)printf("%d %d\n",q[u].l,q[u].r);system("pause");*/for (int u=g;u<=R;u++){while(ll>=q[u].l) {Ins(ll);ll--;}while (rr<q[u].r) {rr++;Ins(rr);}ans[q[u].id]=find(q[u].k);}while (!o.empty())  {
   int xx=o.front();vis[xx]=0;o.pop();}   root=num=0;
}
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
   x=x*10+ch-'0';ch=getchar();}return x*f;
}
inline void write(int x)
{if (!x) return (void)puts("0");if (x < 0) putchar('-'), x = -x;static short s[12], t;while (x) s[++t] = x % 10, x /= 10;while (t) putchar('0' + s[t--]);putchar('\n');
}
int main()
{memset(vis,0,sizeof(vis));num=0;memset(last,-1,sizeof(last));n=read();for (int u=1;u<n;u++){int x,y;x=read();y=read();init(x,y);init(y,x);}num=0;dep[1]=1;dfs(1);m=read();for (int u=1;u<=m;u++){int x,y,a,b;x=read();y=read();a=read();b=read();int lca=get(x,y);s[L[x]].push_back(make_pair(a,b));s[L[y]].push_back(make_pair(a,b));//  printf("LCA:%d\n",lca);s[L[lca]].push_back(make_pair(-a,b));s[L[fa[lca][0]]].push_back(make_pair(-a,b));}Q=read();for (int u=1;u<=Q;u++){int w,k;w=read();k=read();q[u].id=u;q[u].l=L[w];q[u].r=R[w];q[u].k=k;}
/*  for (int u=1;u<=Q;u++)printf("lalal:%d %d %d\n",q[u].l,q[u].r,q[u].k);*/solve(1,n,1,Q);for (int u=1;u<=Q;u++) write(ans[u]);return 0;
}