Description：

给一棵模板树，一颗大树初始等于模板树，先有一些操作把模板树中以 $u$ 为根的子树接到大树的第 $y$ 号节点上，新节点的编号 $=$ 大树原总结点数 $+$ 这个节点在模板树那颗子树里的排名，然后每次询问大树上两个节点的距离。

$1\leqslant n,m,q\leqslant 10^5$

Solution：

首先大树的节点数最大可能达到 $10^{10}$ ，所以肯定不能建树，每次在挂点的时候，只挂一个点代表整棵树，同时记录下这个点所代表的点的编号区间，对模板树建立主席树，这样我们如果想要在大树上查询某个点，就可以在模板树上查询 $dfs$ 序区间第 $k$ 大找到对应的节点，这样我们就解决了挂树的问题，现在考虑回答询问，首先我们要求出 $dep[i]$ 表示代表点所代表的树的根节点到大树的根的实际距离，这个可以在插入的时候求出，然后我们会发现我们还需要减去在一个块内部祖先重合的问题，这个只要求出他们在块内的 $LCA$ 即可。

说起来容易。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,q;

#define MAXN 100010

namespace PT//PresidentTree

{

	struct node

	{

		int lc,rc;

		int sum;

		node(){sum = 0;}

	}t[MAXN * 20];

	#define mid ((l + r) >> 1)

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root[MAXN];

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		if(l == r)return;

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		return;

	}

	void insert(int &rt,int p,int l,int r)

	{

		int k = newnode();t[k] = t[rt];rt = k;

		++t[rt].sum;

		if(l == r)return;

		if(p <= mid)insert(t[rt].lc,p,l,mid);

		else insert(t[rt].rc,p,mid + 1,r);

		return;

	}

	int query(int rtr,int rtl,int k,int l,int r)

	{

		if(l == r)return l;

		int ls = t[t[rtr].lc].sum - t[t[rtl].lc].sum;

		if(k <= ls)return query(t[rtr].lc,t[rtl].lc,k,l,mid);

		else return query(t[rtr].rc,t[rtl].rc,k - ls,mid + 1,r);

	}

}

namespace TT//TemplateTree

{

	struct edge

	{

		int to,nxt;

	}e[MAXN << 1];

	int edgenum = 0;

	int lin[MAXN] = {0};

	void add(int a,int b)

	{

		e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

		e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

		return;

	}

	int f[MAXN][18];

	int dfn[MAXN],rnk[MAXN],siz[MAXN],dep[MAXN];

	void dfs(int k)

	{

		dfn[++dfn[0]] = k;rnk[k] = dfn[0];

		dep[k] = dep[f[k][0]] + 1;

		siz[k] = 1;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(e[i].to == f[k][0])continue;

			f[e[i].to][0] = k;

			dfs(e[i].to);

			siz[k] += siz[e[i].to];

		}

		return;

	}

	void build_doubling()

	{

		for(int k = 1;k <= 17;++k)

			for(int i = 1;i <= n;++i)

				f[i][k] = f[f[i][k - 1]][k - 1];

		return;

	}

	int LCA(int a,int b)

	{

		if(dep[a] < dep[b])swap(a,b);

		for(int k = 17;k >= 0;--k)if(dep[f[a][k]] >= dep[b])a = f[a][k];

		if(a == b)return a;

		for(int k = 17;k >= 0;--k)if(f[a][k] != f[b][k])a = f[a][k],b = f[b][k];

		return f[a][0];

	}

	void build_president_tree()

	{

		PT::build(PT::root[0],1,n);

		for(int i = 1;i <= n;++i)

		{

			PT::root[i] = PT::root[i - 1];

			PT::insert(PT::root[i],dfn[i],1,n);

		}

		return;

	}

	int getnum(int rt,int k)

	{

		int l = rnk[rt],r = rnk[rt] + siz[rt] - 1;

		return PT::query(PT::root[r],PT::root[l - 1],k,1,n);

	}

	int dis(int a,int b)

	{

		return dep[a] + dep[b] - 2 * dep[LCA(a,b)];

	}

}

typedef long long ll; 

namespace MT//MainTree

{

	int f[MAXN][18],dep[MAXN];

	struct node

	{

		ll fa;

		int rt;

		ll l,r;

		int id;

		bool operator < (const node &b)const

		{

			return r < b.r;

		}

	}t[MAXN];

	set<node> s;

	int ptr = 0;

	ll tot = 0;

	ll dist[MAXN];

	void newnode(int rt,ll fa)

	{

		int k = ++ptr;

		t[k].l = tot + 1;t[k].r = tot + TT::siz[rt];

		if(fa != 0)f[k][0] = s.lower_bound((node){0,0,fa,fa,0}) -> id;

		else f[k][0] = 0;

		t[k].id = k;t[k].fa = fa;t[k].rt = rt;

		tot = t[k].r;

		dep[k] = dep[f[k][0]] + 1;

		int pfa = f[k][0];

		if(pfa != 0)dist[k] = dist[pfa] + TT::dis(t[pfa].rt,TT::getnum(t[pfa].rt,fa - t[pfa].l + 1)) + 1;

		s.insert(t[k]);

		return;

	}

	void build_doubling()

	{

		for(int k = 1;k <= 17;++k)

			for(int i = 1;i <= ptr;++i)

				f[i][k] = f[f[i][k - 1]][k - 1];

		return;

	}

	int LCA(int a,int b)

	{

		if(dep[a] < dep[b])swap(a,b);

		for(int i = 17;i >= 0;--i)if(dep[f[a][i]] >= dep[b])a = f[a][i];

		if(a == b)return a;

		for(int i = 17;i >= 0;--i)if(f[a][i] != f[b][i])a = f[a][i],b = f[b][i];

		return f[a][0];

	}

	int skip_to_son(int k,int fa)

	{

		for(int i = 17;i >= 0;--i)if(dep[f[k][i]] > dep[fa])k = f[k][i];

		return k;

	}

	ll query(ll a,ll b)

	{

		int ta = s.lower_bound((node){0,0,a,a,0}) -> id;

		int tb = s.lower_bound((node){0,0,b,b,0}) -> id;

		int pa = TT::getnum(t[ta].rt,a - t[ta].l + 1);

		int pb = TT::getnum(t[tb].rt,b - t[tb].l + 1);

		if(ta == tb)

		{

			return TT::dis(pa,pb);

		}

		int lca = LCA(ta,tb);

		if(lca == ta)

		{

			int son = skip_to_son(tb,ta);

			son = TT::getnum(t[ta].rt,t[son].fa - t[ta].l + 1);

			return dist[tb] - dist[ta] + TT::dis(t[tb].rt,pb) + TT::dis(t[ta].rt,pa) - 2 * TT::dis(t[ta].rt,TT::LCA(son,pa));

		}

		if(lca == tb)

		{

			int son = skip_to_son(ta,tb);

			son = TT::getnum(t[tb].rt,t[son].fa - t[tb].l + 1);

			return dist[ta] - dist[tb] + TT::dis(t[ta].rt,pa) + TT::dis(t[tb].rt,pb) - 2 * TT::dis(t[tb].rt,TT::LCA(son,pb));

		}

		int son1 = skip_to_son(ta,lca);son1 = TT::getnum(t[lca].rt,t[son1].fa - t[lca].l + 1);

		int son2 = skip_to_son(tb,lca);son2 = TT::getnum(t[lca].rt,t[son2].fa - t[lca].l + 1);

		ll ans = 0;

		ans += dist[ta] + dist[tb] - 2 * dist[lca];

		ans += TT::dis(t[ta].rt,pa) + TT::dis(t[tb].rt,pb) - 2 * TT::dis(t[lca].rt,TT::LCA(son1,son2));

		return ans;

	}

}

int main()

{

	scanf("%d%d%d",&n,&m,&q);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		TT::add(a,b);

	}

	TT::dfs(1);

	TT::build_doubling();

	TT::build_president_tree();

	MT::newnode(1,0);

	int k;

	ll fa;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%lld",&k,&fa);

		MT::newnode(k,fa);

	}

	MT::build_doubling();

	ll x,y;

	for(int i = 1;i <= q;++i)

	{

		scanf("%lld%lld",&x,&y);

		printf("%lld\n",MT::query(x,y));

	}

	return 0;

}