1986.Distance Queries
大意：
给一颗树。。每次询问两点之间的距离。。
很明显是要求lca的。。又不是要求在线算法。。于是我就用tarjan了。。
#include<cstdio>
#include<utility>
#include<vector>
using namespace std;
const int maxn=40000;
typedef pair<int,int> pi;
int F[maxn];
inline void makeset(int x)
{
F[x]=x;
}
int find(int x)
{
if(x!=F[x]) F[x]=find(F[x]);
return F[x];
}
void Union(int x,int y)
{
x=find(x);y=find(y);
F[y]=x;
}
int cnt=0;
vector<pi> Ask[maxn],E[maxn];
int Ans[maxn],Dep[maxn];
bool vis[maxn]={0};
void addQuery(int x,int y)
{
Ask[x].push_back(pi(y,cnt));
Ask[y].push_back(pi(x,cnt));
cnt++;
}
void addEdge(int s,int t,int c)
{
E[s].push_back(pi(t,c));
E[t].push_back(pi(s,c));
}
int n,m,k;
void dfs(int x,int dep)
{
vis[x]=true;
Dep[x]=dep;
makeset(x);
for(int v,i=0;i<E[x].size();i++)
if(!vis[v=E[x][i].first])
{
dfs(v,dep+E[x][i].second);
Union(x,v);
}
for(int lca,v,i=0;i<Ask[x].size();i++)
if(vis[v=Ask[x][i].first])
{
lca=find(v);
Ans[Ask[x][i].second]=Dep[x]+Dep[v]-2*Dep[lca];
}
}
int main()
{
scanf("%d %d",&n,&m);
int s,t,l;char c;
while(m–)
{
scanf("%d %d %d %c",&s,&t,&l,&c);s–;t–;
addEdge(s,t,l);
}
scanf("%d",&k);
for(int i=0;i<k;i++)
{
scanf("%d %d",&s,&t);s–;t–;
addQuery(s,t);
}
dfs(0,0);
for(int i=0;i<k;i++)
{
printf("%dn",Ans[i]);
}
}1987.Distance Statistics
这道有点意思：
给一颗树。。求出其中距离不超过K的点有多少对。。
明显是要用分治。。首先多叉转二叉。。所有点到兄弟的边长度都为0。。
之所以要多叉转二叉是因为如果不转的话。。有些情况（例如星形树。。）你就悲剧了。。
这样两点之间的距离还是不变的。。
然后用基于边的分支。。每次找出中心边。。再分成两棵子树。。
然后两个点都在子树内部的可以递归解决。。需要算的是两个点在不同子树的。。
两个子树所有节点都按到根的距离排序。。然后就可以扫描了。。
可惜我的Code写次了。。时间超了1倍。。需要去改改。。
没AC就不发了。。