DAY5测试T2 Tree（LCA+线段树/树上差分）
【问题描述】
小s是A星球的霸主。A星球上有n个城市，城市之间有一些道路。小s发现城市和道路刚好组成了一棵树。并且他发现如果有任意一条道路损坏，城市和城市之间就不连通了。A星球上还有m对工作站(A, B)。每对工作站在工作的时候，需要人员从A城市走到B城市。
现在A星球有Q个任务，每个任务可以由第L对工作站到第R对工作站任意一个来完成。小s想知道对于每个任务，损坏了哪些边会导致任务不能完成。他想把这个问题交给你，但你只需要告诉他损坏的边的总长度即可。
【输入格式】
输入的第一行包含1个整数n，表示城市个数。
接下来n-1行，每行包含3个整数x, y, z，表示边(x, y)和边的长度z。
接下来一行一个整数m，表示m对工作站。
接下来m行，每行包含两个整数A, B
接下来一行一个整数Q，表示任务数。
接下来Q行，每行两个整数L，R。表示第i个任务可以由第L对到第R对工作站完成。
【输出格式】
输出Q行，第i行表示第i个任务的答案。
【样例输入】
4
1 2 5
2 3 2
1 4 3
2
1 2
3 4
1
1 2
【样例输出】
5
【数据范围与约定】
30%: n, m, Q <= 200
60%: n, m, Q <= 1000
100%: n, m, Q <= 50000
一看到题就想起之前做的NOIP2015 运输计划了。简化题意为求第L~R条给定路径公共边的权值和。那么跑一遍dfs预处理出 dis[ i ] 数组表示节点 i 到根节点的距离，则可得每对工作站的路径长。
然后开始读入查询，对于每对查询都做一遍差分。差分数组为 dif 。例如对于某对工作站 ( x, y )，dif [ x ]+=1， dif [ y ]+=1 ，dif[ LCA( x, y ) ]-=2。处理完 [ L,R ] 后求一遍子树权值和。若某个点权值和等于 R-L+1 ，则其到父节点的那条边必为公共边。由于倍增求LCA中会处理出数组 f[ x][ 0 ]，故易得其父节点。枚举 n 求和即可。
时间复杂度大致是 O( nq )，能过六十分。但是要开long long。以后这种累加的都应该注意一点。
正解很绝妙。
通过观察可以发现对于两条路径：（x1，y1）和（x2，y2），在LCA（x1，x2），LCA（x1，y2），LCA（y1，x2），LCA（y1，y2）中取深度最大的两个点，这两点之间的路径即为公共路径。画个图就能明白。
这么说题目暗示还是给的很明显的，“第L对到第R对”，还有这么大的查询量，肯定要用数据结构维护了。我们考虑线段树。
用线段树维护 1~m 对工作站。每段区间（x，y）都表示第 x 对~第 y 对按上述方法求出的公共路径的两个端点。剩下都是线段树的常规操作。
调了很久……居然是因为忘记删一个比较微妙的打表。
#include<bits/stdc++.h>
using namespace std;
const int maxn=50001;
int n,m,q;
int x,y,z;
int Link[maxn];
struct edge{
int y,next,v;
}e[maxn<<1];
int Tot;
int dep[maxn];
long long dis[maxn];
int f[maxn][30];
bool vis[maxn];
int K;
struct Node{
int N1,N2;
}Tree[maxn<<2],Temp2,Res;
int L,R;
int Temp1[4];
inline void read(int &x)
{
x=0;int f=1;char s=getchar();
for(;s<'0'||s>'9';s=getchar()) if(s=='-') f=-1;
for(;s>='0'&&s<='9';s=getchar()) x=(x<<3)+(x<<1)+s-48;
x*=f;
}
inline void Insert(int x,int y,int v)
{
e[++Tot].y=y;e[Tot].v=v;
e[Tot].next=Link[x];Link[x]=Tot;
}
inline bool mycmp(int a,int b)
{
return(dep[a]>dep[b]);
}
int get_LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=K;i>=0;--i)
if(dep[x]-(1<<i)>=dep[y]) x=f[x][i];
if(x==y) return x;
for(int i=K;i>=0;--i)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
inline Node Unite(Node a,Node b)
{
Temp1[0]=get_LCA(a.N1,b.N1);Temp1[1]=get_LCA(a.N1,b.N2);
Temp1[2]=get_LCA(a.N2,b.N1);Temp1[3]=get_LCA(a.N2,b.N2);
sort(Temp1,Temp1+4,mycmp);
Temp2.N1=Temp1[0];Temp2.N2=Temp1[1];
return Temp2;
}//合并。
void dfs_mul(int x)
{
vis[x]=1;
for(int i=1;(1<<i)<=dep[x];++i) f[x][i]=f[f[x][i-1]][i-1];
for(int i=Link[x];i;i=e[i].next)
if(!vis[e[i].y]){
dep[e[i].y]=dep[x]+1;dis[e[i].y]=dis[x]+1LL*e[i].v;f[e[i].y][0]=x;
dfs_mul(e[i].y);
}
}
void Build(int Root,int l,int r)
{
if(l==r){
read(Tree[Root].N1);read(Tree[Root].N2);
return;
}
int Mid=(l+r)>>1;
Build(Root<<1,l,Mid);Build(Root<<1|1 ,Mid+1,r);
Tree[Root]=Unite(Tree[Root<<1],Tree[Root<<1|1]);
}
Node Query(int Root,int l,int r)
{
if(L<=l&&r<=R) return Tree[Root];
int Mid=(l+r)>>1;
if(L>Mid) return Query(Root<<1|1,Mid+1,r);
else if(R<=Mid) return Query(Root<<1,l,Mid);
else return Unite(Query(Root<<1,l,Mid),Query(Root<<1|1,Mid+1,r));
}
void Init()
{
read(n);
Tot=0;
for(int i=1;i<n;++i)
{
read(x);read(y);read(z);
Insert(x,y,z);Insert(y,x,z);
}
}
void Prepare()
{
memset(vis,0,sizeof(vis));
memset(dep,0,sizeof(dep));
memset(f,0,sizeof(f));
memset(dis,0,sizeof(dis));
dep[1]=1;f[1][0]=-1;
dfs_mul(1);
K=(int)(log(n)/log(2))+1;
read(m);
Build(1,1,m);
}
void Work()
{
read(q);
for(int i=1;i<=q;++i)
{
read(L);read(R);
Res=Query(1,1,m);
printf("%lld\n",1LL*dis[Res.N1]+1LL*dis[Res.N2]-1LL*(dis[get_LCA(Res.N1,Res.N2)]<<1));
}
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
Init();
Prepare();
Work();
fclose(stdin);fclose(stdout);
return 0;
}这几天唯一一道确定能拿到部分分的题，居然因为 long long 的问题挂掉了。非常不应该。太久了都没有概念了啊。