[Ceoi2004]Journey

浅浅的花香味﹌ 2021-12-24 16:21 166阅读 0赞

## 题目描述 ##

### 给出N个点，及你的出发点K. ###

### 接下来N-1行描述有关边的开始点，结束点，边长.保证图中不会有环 ###

### 接下来给出数字J，代表你要走多少个点. ###

### 接下来J个数字，代表你要走过的点的编号.当然你可以自己选择行进的路线 ###

### 不一定按给定编号顺序前行,求走过的最短距离。 ###

## 输入格式 ##

### 第一行给出N,K。2 <= N<= 50000,1<=K<=N ###

### 接下来N-1行，每行三个数，进来描述这个地图中的边,边长距离<=1000 ###

### 接下来给出一个数字J,1<=J <= N-1代表你希望走过的J个点。 ###

### 最后一行给出J个数字，代表点的编号。1<=编号<=N,且不等于K ###

## 输出格式 ##

### 如题 ###

--------------------

### 显然，我们只往要去的点走，并且一条边最多经过两次(去和回)。我们可以求出所有要走过的点到根节点的路径，把它们取个交集，得到的集合里的边权乘2再减去最深的目的地到根节点的距离就是答案了。 ###

### ans=sum\*2-maxlenth ###

### maxlenth容易得到，这题的关键就是求出sum。 ###

### 其实可以用到一点树形dp的思想，如果当前点被经过，那么当前点的父亲也会被经过。即： ###

for(each v∈son[u]) do

if(vis[v]=true)then vis[u]=true;

### 初始化所有目的地的vis都为真。最后再统计一下vis，计算出sum即可。 ###

#### 附上代码： ####

#include<iostream>

#include<cstring>

#include<cstdio>

#define maxn 50001

using namespace std;

struct edge{

int to,dis,next;

edge(){}

edge(const int &_to,const int &_dis,const int &_next){

to=_to,dis=_dis,next=_next;

}

}e[maxn<<1];

int head[maxn],k;

bool vis[maxn];

int dep[maxn],a[maxn],val[maxn];

int n,m,s;

inline int read(){

while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }

while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

return x*f;

}

inline void add(const int &u,const int &v,const int &w){

e[k]=edge(v,w,head[u]);

head[u]=k++;

}

void dfs(int u,int pre){

for(register int i=head[u];~i;i=e[i].next){

int v=e[i].to;

if(v==pre) continue;

dep[v]=dep[u]+1;

dfs(v,u);

if(vis[v]) vis[u]=true;

}

void dfs2(int u,int pre){

for(register int i=head[u];~i;i=e[i].next){

int v=e[i].to;

if(v==pre) continue;

dep[v]=dep[u]+e[i].dis;

dfs2(v,u);

}

int main(){

memset(head,-1,sizeof head);

n=read(),s=read();

for(register int i=1;i<n;i++){

int u=read(),v=read(),w=read();

add(u,v,w),add(v,u,w);

}

m=read();

for(register int i=1;i<=m;i++){

a[i]=read(),vis[a[i]]=true;

}

dfs(s,0);

for(register int i=0;i<k;i+=2){

int u=e[i].to,v=e[i^1].to;

if(dep[u]>dep[v]) swap(u,v);

val[v]=e[i].dis;

}//把边权赋给点权

long long ans=0;

for(register int i=1;i<=n;i++) if(vis[i]){

ans+=val[i];

}

memset(dep,0,sizeof dep);

dfs2(s,0);

int maxdep=0;

for(register int i=1;i<=n;i++) if(vis[i]){

maxdep=max(maxdep,dep[i]);

}

printf("%d\n",ans*2-maxdep);

return 0;

}

#### 时间复杂度为O(n) ####

--------------------

#### 这是离线算法......\#滑稽 正片开始 ####

#### 为什么不考虑一下神奇的在线呢？既然是50000的数据，我们就跑个在线给他看。 ####

### 每读入一个目的地时，我们就可以把它到根节点的路径的vis全部赋成真。先考虑暴力做法——一个一个地往上赋值，时间复杂度为O(n)，总共就是O(n^2)，肯定会爆.......不如加加速？ ###

### 试试树剖吧。我们可以用线段树来维护区间内一共要被经过的点的权值和(预处理将边权转化为点权)。怎么维护呢？既然是树链剖分，那么一条链子上的时间戳dfn值都是一串连续的数字吧？而且我们肯定修改时会一条链子一条链子地改。所以我们可以维护一个数组：时间戳前缀和c。类似于普通的前缀和，c\[i\]=c\[i-1\]+val\[id\[i\]\]，其中val表示点权，id为dfn的反函数。如果我要修改dfn从l到r的区间，那么： ###

### \*t\[d\].c为我们要维护的点权和，d是当前区间的编号。 ###

### \*不要忘了打懒标记和上传权值。 ###

### 最后的答案就是1~tot的权值和(tot为dfn最大值)，即t\[1\].c。 ###

### 这样做的话，每次操作的复杂度就是O(lognlogn)，总共O(nlognlogn)，50000的数据是可以跑过的 ###

转载于:https://www.cnblogs.com/akura/p/10809540.html