=== ===
這里放傳送門(mén)
=== ===
題解
這題某天學(xué)長(zhǎng)出過(guò)胡策。。第一眼拿到題，woc，這不就是個(gè)裸倍增？第二眼，woc，節(jié)點(diǎn)數(shù)最大到1e10，這是要死的節(jié)奏。。。
這題寫(xiě)起來(lái)真 · 麻煩死人。。基本思路是每次把復(fù)制的模板樹(shù)的那個(gè)子樹(shù)縮成一個(gè)點(diǎn)，初始的那一整個(gè)模板樹(shù)也縮成一個(gè)點(diǎn)，那么大樹(shù)上最多只會(huì)有m+1個(gè)點(diǎn)。然后每次查詢的時(shí)候就可以先定位在模板樹(shù)上的節(jié)點(diǎn)，再在大樹(shù)上跑倍增，最后再定位到模板樹(shù)上的具體節(jié)點(diǎn)，然后時(shí)間復(fù)雜度就是科學(xué)的O(nlogn)了。。
具體來(lái)說(shuō)，首先縮點(diǎn)以后大樹(shù)的邊上就出現(xiàn)了邊權(quán)，相鄰兩個(gè)節(jié)點(diǎn)之間的邊權(quán)設(shè)定為當(dāng)把大樹(shù)展開(kāi)時(shí)這兩個(gè)節(jié)點(diǎn)所代表子樹(shù)的根節(jié)點(diǎn)之間的距離。為了知道這一個(gè)我們還要知道當(dāng)大樹(shù)上一個(gè)節(jié)點(diǎn)下面掛了另一個(gè)節(jié)點(diǎn)的時(shí)候它實(shí)際上是從哪一個(gè)具體的節(jié)點(diǎn)接入的，這樣才能計(jì)算它進(jìn)入這個(gè)節(jié)點(diǎn)代表的子樹(shù)以后再跑多久才能到達(dá)這棵子樹(shù)的根節(jié)點(diǎn)。這個(gè)在處理修改操作的時(shí)候記錄下來(lái)就可以。這樣處理出了一棵帶邊權(quán)的大樹(shù)，然后對(duì)大樹(shù)進(jìn)行dfs處理出倍增所需要的數(shù)組。
而在這里還有一個(gè)問(wèn)題就是如何定位到模板樹(shù)中的具體節(jié)點(diǎn)，因?yàn)槊看谓尤胱訕?shù)以后節(jié)點(diǎn)會(huì)被按照原來(lái)的大小順序重新編號(hào)，而當(dāng)我們想定位某個(gè)節(jié)點(diǎn)的時(shí)候我們知道它現(xiàn)在的編號(hào)，那么就可以通過(guò)在修改操作中進(jìn)行二分來(lái)知道它是哪一個(gè)操作接進(jìn)去的，然后就可以知道它具體在模板樹(shù)的哪棵子樹(shù)里，然后還可以通過(guò)它現(xiàn)在的編號(hào)知道它是這棵子樹(shù)里編號(hào)第幾大的點(diǎn)。要知道具體是哪個(gè)點(diǎn)就要查詢子樹(shù)中第k大了，那么就要對(duì)dfs序建立主席樹(shù)來(lái)搞這個(gè)東西。
每次查詢的時(shí)候首先定位當(dāng)前所在模板樹(shù)子樹(shù)的節(jié)點(diǎn)，然后計(jì)算出它到根節(jié)點(diǎn)的距離，因?yàn)檫@部分相當(dāng)于是大樹(shù)上的“半個(gè)節(jié)點(diǎn)”，不能直接跑倍增。接下來(lái)用倍增算出“整個(gè)節(jié)點(diǎn)”的部分。但是這樣會(huì)有一些多算了，因?yàn)橹苯优鼙对龅臅r(shí)候是相當(dāng)于跑到那個(gè)子樹(shù)的根節(jié)點(diǎn)的，但實(shí)際上可能還沒(méi)到根節(jié)點(diǎn)就走到LCA了。所以我們需要找到路徑兩邊的節(jié)點(diǎn)x和y分別是在哪個(gè)節(jié)點(diǎn)接入的，然后就可以算出它實(shí)際上的LCA，多算的那一部分就是實(shí)際LCA和子樹(shù)根節(jié)點(diǎn)距離的兩倍，減掉就可以了。
代碼
#include<cstdio>#include<cstring>#include<algorithm>#define Pow 17using namespace std;int n,m,q,p[100010],a[200010],next[200010],tot,deep[100010],size[100010],f[100010][20];int w[100010],root[100010],cnt,out[100010],in[100010],cur[100010];long long sum;struct Operate{ int a; long long b,l,r;}k[100010];struct segtree{ int l,r,val;}t[4000010];void add(int x,int y){tot++;a[tot]=y;next[tot]=p[x];p[x]=tot;}/*void dfs(int u){ deep[u]=deep[f[u][0]]+1; for (int i=1;i<=Pow;i++) f[u][i]=f[f[u][i-1]][i-1]; size[u]=1;w[++w[0]]=u;in[u]=w[0]; for (int i=p[u];i!=0;i=next[i]) if (a[i]!=f[u][0]){ f[a[i]][0]=u; dfs(a[i]); size[u]+=size[a[i]]; } out[u]=w[0];}*/void dfs(){ int u=1; bool flag; while (true){ if (deep[u]==0){ deep[u]=deep[f[u][0]]+1; for (int i=1;i<=Pow;i++) f[u][i]=f[f[u][i-1]][i-1]; size[u]=1;w[++w[0]]=u; in[u]=w[0];cur[u]=p[u]; } flag=false; for (int i=cur[u];i!=0;i=next[i]){ cur[u]=next[i]; if (a[i]!=f[u][0]){ f[a[i]][0]=u; u=a[i];flag=true;break; } } if (flag==false){ out[u]=w[0]; if (u==1) break; else{ int v=f[u][0]; size[v]+=size[u];u=v; } } }}void insert(int &i,int j,int l,int r,int v){ i=++cnt;t[i]=t[j]; t[i].val++; if (l==r) return; int mid=(l+r)>>1; if (v<=mid) insert(t[i].l,t[j].l,l,mid,v); else insert(t[i].r,t[j].r,mid+1,r,v);}int Find_rank(int i,int j,int l,int r,int k){ if (l==r) return l; int tmp=t[t[j].l].val-t[t[i].l].val,mid=(l+r)>>1; if (tmp>=k) return Find_rank(t[i].l,t[j].l,l,mid,k); else return Find_rank(t[i].r,t[j].r,mid+1,r,k-tmp);}int find(long long x){ int l,r,mid; l=1;r=m+1; while (l<=r){ int mid=(l+r)>>1; if (k[mid].l>x) r=mid-1; else if (k[mid].r<x) l=mid+1; else return mid; } return 0;}int Findpoint(int i,long long x){ long long rt,rk; rt=k[i].a;rk=x-k[i].l+1; return Find_rank(root[in[rt]-1],root[out[rt]],1,n,rk);}namespace Bigtree{ int p[100010],a[200010],next[200010],w[200010],tot,deep[100010],f[100010][20]; int cur[100010],g[100010][20],last[100010][20]; void add(int x,int y,int v){ tot++;a[tot]=y;next[tot]=p[x];w[tot]=v;p[x]=tot; }/* void dfs(int u){ deep[u]=deep[f[u][0]]+1; for (int i=1;i<=Pow;i++){ f[u][i]=f[f[u][i-1]][i-1]; g[u][i]=g[u][i-1]+g[f[u][i-1]][i-1]; last[u][i]=last[f[u][i-1]][i-1]; } for (int i=p[u];i!=0;i=next[i]) if (a[i]!=f[u][0]){ f[a[i]][0]=u; g[a[i]][0]=w[i]; last[a[i]][0]=a[i]; dfs(a[i]); } }*/ void dfs(){ int u=1; bool flag; while (true){ if (deep[u]==0){ deep[u]=deep[f[u][0]]+1;cur[u]=p[u]; for (int i=1;i<=Pow;i++){ f[u][i]=f[f[u][i-1]][i-1]; g[u][i]=g[u][i-1]+g[f[u][i-1]][i-1]; last[u][i]=last[f[u][i-1]][i-1]; } } flag=false; for (int i=cur[u];i!=0;i=next[i]){ cur[u]=next[i]; if (a[i]!=f[u][0]){ f[a[i]][0]=u; g[a[i]][0]=w[i]; last[a[i]][0]=a[i]; u=a[i];flag=true;break; } } if (flag==false) if (u==1) break; else u=f[u][0]; } } long long FindLCA(int &lca,long long &f1,long long &f2,int x,int y){ long long ans=0; bool s=false; f1=x;f2=y; if (deep[x]!=deep[y]){ if (deep[x]<deep[y]){ swap(x,y);swap(f1,f2);s=true; } for (int i=Pow;i>=0;i--) if (deep[f[x][i]]>=deep[y]){ f1=last[x][i];ans+=g[x][i];x=f[x][i]; } } for (int i=Pow;i>=0;i--) if (f[x][i]!=f[y][i]){ ans+=g[x][i]+g[y][i]; f1=last[x][i];f2=last[y][i]; x=f[x][i];y=f[y][i]; } while (x!=y){ ans+=g[x][0]+g[y][0]; f1=last[x][0];f2=last[y][0]; x=f[x][0];y=f[y][0]; } if (s==true) swap(f1,f2); lca=x;return ans; }}long long Calcdis(int i,long long x){ int pt=Findpoint(i,x); return deep[pt]-deep[k[i].a];}void Link(int i,int x,long long y){ int u=find(y),dis; dis=Calcdis(u,y); Bigtree::add(i,u,dis+1); Bigtree::add(u,i,dis+1);}long long findlca(long long r1,long long r2,int p){//求出r1，r2兩個(gè)在區(qū)間k[p]里面的節(jié)點(diǎn)的lca并返回 int x,y; x=Findpoint(p,r1); y=Findpoint(p,r2); if (deep[x]!=deep[y]){ if (deep[x]<deep[y]) swap(x,y); for (int i=Pow;i>=0;i--) if (deep[f[x][i]]>=deep[y]) x=f[x][i]; } for (int i=Pow;i>=0;i--) if (f[x][i]!=f[y][i]){ x=f[x][i];y=f[y][i]; } while (x!=y){ x=f[x][0];y=f[y][0]; } return deep[x]-deep[k[p].a];}int main(){ scanf("%d%d%d",&n,&m,&q); for (int i=1;i<n;i++){ int x,y;scanf("%d%d",&x,&y); add(x,y);add(y,x); } dfs();sum=n; for (int i=1;i<=n;i++) insert(root[i],root[i-1],1,n,w[i]); k[1].l=1;k[1].r=n;k[1].a=1; for (int i=2;i<=m+1;i++){ scanf("%d%lld",&k[i].a,&k[i].b);//注意用long long k[i].l=sum+1;k[i].r=sum+size[k[i].a]; sum+=size[k[i].a]; } for (int i=2;i<=m+1;i++) Link(i,k[i].a,k[i].b); Bigtree::dfs(); for (int i=1;i<=q;i++){ long long x,y,f1,f2,ans=0; int r1,r2,lca; scanf("%lld%lld",&x,&y); r1=find(x);r2=find(y); ans+=Calcdis(r1,x); ans+=Calcdis(r2,y);//計(jì)算出兩個(gè)端點(diǎn)在它們小區(qū)間里到根節(jié)點(diǎn)的距離 ans+=Bigtree::FindLCA(lca,f1,f2,r1,r2);//計(jì)算出兩個(gè)端點(diǎn)在大樹(shù)里整塊的距離 if (r1==lca) f1=x;else f1=k[f1].b; if (r2==lca) f2=y;else f2=k[f2].b; ans-=2*findlca(f1,f2,lca); //減去進(jìn)入lca的模板樹(shù)區(qū)間的兩個(gè)點(diǎn)的lca到模板樹(shù)區(qū)間根節(jié)點(diǎn)的距離 偏偏在最后出現(xiàn)的補(bǔ)充說(shuō)明這題好難寫(xiě)啊= =
