| 记录编号 |
261179 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[NOIP 2015]运输计划 |
最终得分 |
100 |
| 用户昵称 |
 再见 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.427 s |
| 提交时间 |
2016-05-15 17:28:58 |
内存使用 |
16.63 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=300050;
int last[N]; //每个点的父节点
int father[N]; //用于离线LCA and 用于树上找路
int dist[N]; //每个点到根的距离
int deep[N]; //计算深度
int line[N]; //最长路径的每一条边
int dye[N]; //对最长路上的每个点染色
int sum[N]; //前缀和
int ans[N]; //离线LCA答案
bool vis[N]; //离线LCA判断
int all_size; //最长路径上的边数
int line_LCA; //最长路径的LCA
int Dist; //最长路径的长度
int n,m; //n个点,m个路径
struct Node { //存路径
int x,y,lca,dist;
}node[N];
struct Edge { //链表
int a,b;
Edge* next;
};
Edge* g[N]; //存边和边权
Edge* q[N]; // 存询问路径
bool cmp(Node a,Node b){return a.dist>b.dist;}
inline int read() {
char s=getchar();
int x=0;
while(s>'9'||s<'0')s=getchar();
while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
return x;
}
void insert(Edge* &o,int a,int b) { //链表插入
Edge* k=new Edge;
k->a=a,k->b=b,k->next=o,o=k;
}
int find(int x) { //非递归并查集
int j,k=x,r=x;
while(r!=father[r]) r=father[r];
while(k!=r) {
j=father[k];
father[k]=r;
k=j;
}
return r;
}
void unionn(int a,int b) { //并查集合并操作,father[a]=fb顺序不能变因为要在树上找路
int fa=find(a),fb=find(b);
if(fa!=fb) father[fa]=fb;
}
void LCA(int x,int fa) { //离线LCA同时计算每个点 的深度和到根节点的距离
int i;
Edge* w;
deep[x]=deep[fa]+1;
ans[x]=x;
w=g[x];
while(w!=NULL) {
if(w->a!=fa) {
dist[w->a]=dist[x]+w->b;
last[w->a]=x;
LCA(w->a,x);
unionn(w->a,x);
}
w=w->next;
}
vis[x]=true;
w=q[x];
while(w!=NULL) {
if(vis[w->a]) {
node[w->b].lca=ans[find(w->a)];
node[w->b].dist=dist[x]+dist[w->a]-2*dist[node[w->b].lca];
}
w=w->next;
}
}
void search(int x) { //找每条路径与最长路径上公共线段 ,用并查集加速树上找路
int a=find(node[x].x),b=find(node[x].y),c=node[x].lca;
while(a&&!dye[a]) {
if(deep[a]<deep[c]) break;
unionn(a,last[a]);
a=find(a);
}
while(b&&!dye[b]) {
if(deep[b]<deep[c]) break;
unionn(b,last[b]);
b=find(b);
}
if(deep[c]<deep[line_LCA]&&(dye[a]||dye[b])) !dye[a]?a=line_LCA:b=line_LCA;
node[x].x=min(dye[a],dye[b]),node[x].y=max(dye[a],dye[b])-1;
}
bool ok(int x) { //二分答案判断
int i,L=1,R=all_size;
for(i=1;i<=all_size;i++) //对于最长路上的每条线段,如果它的长度>=Dist-x,说明该线段可选
if(line[i]>=Dist-x) sum[i]=sum[i-1]+1;
else sum[i]=sum[i-1];
if(sum[R]-sum[L-1]<=0) return 0;
for(i=1;i<m&&node[i].dist>x;i++) {
L=max(L,node[i].x);
R=min(R,node[i].y); //[L,R]和[l,r]求交
if(L>R) return 0;
if(sum[R]-sum[L-1]<=0) return 0; //[L,R]上没有可选点
}
return 1;
}
int main() {
freopen("transport.in","r",stdin);
freopen("transport.out","w",stdout);
int i,x,y,z;
n=read(),m=read();
for(i=0;i<=n;i++) {
father[i]=i; //初始化father,此时father用于离线LCA
g[i]=q[i]=NULL;
}
for(i=1;i<n;i++) {
x=read(),y=read(),z=read();
insert(g[x],y,z);
insert(g[y],x,z);
}
for(i=0;i<m;i++) {
node[i].x=read();
node[i].y=read();
insert(q[node[i].x],node[i].y,i);
insert(q[node[i].y],node[i].x,i);
}
LCA(1,0);
sort(node,node+m,cmp);
line_LCA=node[0].lca;
x=node[0].x,y=node[0].y,Dist=node[0].dist,i=0;
all_size=deep[x]+deep[y]-2*deep[line_LCA];
while(x!=line_LCA) { //找最长线段上的的所有线段,并对每个最长路上的点染色
dye[x]=++i;
line[i]=dist[x]-dist[last[x]];
x=last[x];
}
dye[line_LCA]=++i,i=0;
while(y!=line_LCA) {
dye[y]=all_size+1-i;
line[all_size-i++]=dist[y]-dist[last[y]];
y=last[y];
}
for(i=0;i<=n;i++) father[i]=i; //初始化father,此时father用于树上找路
for(i=1;i<m;i++) search(i);
int l=0,r=Dist,mid;
while(l<r) { //二分答案
mid=l+r>>1;
if(ok(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",r);
return 0;
}