解法一：树链剖分+二分+差分
树链剖分快速求解任意两点间的路径的权值和；
然后，二分答案；
此题的难点是如何快速求解重合路径？
差分数组可以否？？？
在此之前先介绍一下相关变量：
int fa[maxn];
int siz[maxn];//siz[i]:i子树的节点个数
int dep[maxn];//dep[i]:节点i在树中的深度
int son[maxn];//son[i]:节点i的重儿子
int w[maxn];//w[i]:i节点与其父节点的权值
int tid[maxn];//tid[i]:节点i的新编号
int top[maxn];//top[i]:节点i所在重链的祖先
int s[maxn];//s[i]:新编号中，[1,i]的权值之和，s[i]=w[1]+w[2]+...+w[i];
如何用差分数组求解重合路径呢？
考虑一下化简得题型，给定 n 个数；
给出 m 个区间 [L,R] ，如何求着 m 个区间公共覆盖的点？
例如 n = 10 , m = 4;
[2,8],[3,7],[4,6],[5,6]
这四个区间得公共覆盖得区间点为 5,6；
定义diff[ ]为差分数组。
对于给出得区间[L,R] , diff[L]++,diff[R+1]--;
最后扫一遍diff[] ，求出diff[]得前缀和sum[]；
如果存在点 x 使得 sum[x] = m，那么点 x 就是这 m 个区间公共覆盖的点；
此题同理，求出不满足二分条件得 cnt 个区间[L,R]，通过diff[]求出这 cnt 个区间公共覆盖的点；
代码如下：
int diff[maxn];
void Update(int u,int v)
{
int x=top[u];
int y=top[v];
if(x == y)//如果 u,v 在同一条重链上
{
if(dep[u] > dep[v])
swap(u,v);
//节点son[u]到节点v的新编号是连续的
diff[tid[son[u]]]++;
diff[tid[v]+]--;
return ;
}
else//如果不在
{
if(dep[x] > dep[y])
{
swap(x,y);
swap(u,v);
}
//节点 top[v]与节点v的新编号是连续的
diff[tid[y]]++;
diff[tid[v]+]--;
Update(u,fa[y]);
}
}
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=3e5+; int n,m;
int fa[maxn];
int siz[maxn];//siz[i]:i子树的节点个数
int dep[maxn];
int son[maxn];//son[i]:节点i的重儿子
int w[maxn];//w[i]:i节点与其父节点的权值
int tid[maxn];//tid[i]:节点i的新编号
int top[maxn];//top[i]:节点i所在重链的祖先
int s[maxn];//s[i]:新编号中，[1,i]的权值之和，s[i]=w[1]+w[2]+...+w[i];
int num;
int head[maxn];
struct Edge
{
int to;
int w;
int next;
}G[*maxn];
void addEdge(int u,int v,int w)
{
G[num].to=v;
G[num].w=w;
G[num].next=head[u];
head[u]=num++;
}
struct Que
{
int u,v;
int w;
}que[maxn];
void DFS1(int u,int f,int d)
{
fa[u]=f;
dep[u]=d;
siz[u]=;
for(int i=head[u];~i;i=G[i].next)
{
int v=G[i].to;
if(v == f)
continue; w[v]=G[i].w;
DFS1(v,u,d+); siz[u] += siz[v];
if(son[u] == - || siz[v] > siz[son[u]])
son[u]=v;
}
}
void DFS2(int u,int a,int &k)
{
top[u]=a;
tid[u]=++k;
s[k]=s[k-]+w[u];
if(son[u] == -)
return ;
DFS2(son[u],a,k);
for(int i=head[u];~i;i=G[i].next)
{
int v=G[i].to;
if(v != son[u] && v != fa[u])
DFS2(v,v,k);
}
}
int Find(int u,int v)//求解节点u到节点v的路径权值和
{
int x=top[u];
int y=top[v];
int ans=; while(x != y)
{
if(dep[x] > dep[y])
{
swap(u,v);
swap(x,y);
}
ans += s[tid[v]]-s[tid[y]-];
v=fa[y];
y=top[v];
}
if(u != v)
{
if(dep[u] > dep[v])
swap(u,v);
ans += s[tid[v]]-s[tid[u]];
} return ans;
} int diff[maxn];
void Update(int u,int v)
{
int x=top[u];
int y=top[v];
if(x == y)//如果 u,v 在同一条重链上
{
if(dep[u] > dep[v])
swap(u,v);
//节点son[u]到节点v的新编号是连续的
diff[tid[son[u]]]++;
diff[tid[v]+]--;
return ;
}
else//如果不在
{
if(dep[x] > dep[y])
{
swap(x,y);
swap(u,v);
}
//节点 top[v]与节点v的新编号是连续的
diff[tid[y]]++;
diff[tid[v]+]--;
Update(u,fa[y]);
}
}
/**
cnt:一共有cnt个权值和 > mid
ans1:这cnt个权值和最大的比mid大多少
ans2:这cnt个路径中权值最大的公共路径
*/
bool Check(int mid)
{
int cnt=;
int ans1=;
for(int i=;i <= m;++i)
{
int u=que[i].u;
int v=que[i].v;
if(que[i].w > mid)
{
cnt++;
ans1=max(ans1,que[i].w-mid);
Update(u,v);
}
}
int ans2=;
int tot=;
for(int i=;i <= n;++i)
{
tot += diff[i];
diff[i]=;
if(tot == cnt)
ans2=max(ans2,s[i]-s[i-]);
}
//只有ans2 >= ans1 才能够使最大的权值和小于等于mid
return ans2 >= ans1;
}
int Solve()
{
DFS1(,,);
int k=;
DFS2(,,k); for(int i=;i <= m;++i)
{
int u=que[i].u;
int v=que[i].v;
que[i].w=Find(u,v);
} int l=-,r=+;
while(r-l > )//二分答案
{
int mid=l+((r-l)>>);
if(Check(mid))
r=mid;
else
l=mid;
}
return r;
}
void Init()
{
num=;
mem(head,-);
mem(diff,);
mem(son,-);
mem(s,);
}
int main()
{
// freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\BZOJ\\4326.in","r",stdin);
while(~scanf("%d%d",&n,&m))
{
Init();
for(int i=;i < n;++i)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
addEdge(v,u,w);
}
for(int i=;i <= m;++i)
scanf("%d%d",&que[i].u,&que[i].v); printf("%d\n",Solve());
}
return ;
}
解法二：树上差分+LCA+二分