bef->NO.6

Veröffentlicht am

NOIp 2015 运输计划

题目背景

公元 20442044 年,人类进入了宇宙纪元。

题目描述

公元20442044 年，人类进入了宇宙纪元。

L 国有 nn 个星球，还有 n-1n−1 条双向航道，每条航道建立在两个星球之间，这 n-1n−1 条航道连通了 LL 国的所有星球。

小 P 掌管一家物流公司， 该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 u_i号星球沿最快的宇航路径飞行到 v_ivi 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 j，任意飞船驶过它所花费的时间为 t_jtj，并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新， L 国国王同意小 P 的物流公司参与 L国的航道建设，即允许小P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后，这 m 个运输计划会同时开始，所有飞船一起出发。当这 m 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。

如果小 PP 可以自由选择将哪一条航道改造成虫洞， 试求出小 PP 的物流公司完成阶段性工作所需要的最短时间是多少？

输入输出格式

输入格式：

第一行包括两个正整数 n, m表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 11 到 nn 编号。

接下来 n-1行描述航道的建设情况，其中第 ii 行包含三个整数 a_i, b_iai,bi 和 t_iti，表示第 ii 条双向航道修建在 a_iai与 b_ibi 两个星球之间，任意飞船驶过它所花费的时间为 t_iti。数据保证

且

接下来 m行描述运输计划的情况，其中第 j 行包含两个正整数

表示第 j 个运输计划是从

号星球飞往

号星球。数据保证

输出格式：

一个整数，表示小 PP 的物流公司完成阶段性工作所需要的最短时间。

输入输出样例

输入样例#1：

复制

1
2
3
4
5
6
7
8
9
6 3 
1 2 3 
1 6 4 
3 1 7 
4 3 6 
3 5 5 
3 6 
2 5 
4 5

输出样例#1：

复制

1
11

说明

所有测试数据的范围和特点如下表所示

img

请注意常数因子带来的程序效率上的影响。

题意

给定一棵树，给定m条链，要求选择树上一条边使边权为零，m条链中的最大值最小。

题解

答案显然满足可行性单调，因此二分答案。

对于每个答案我们怎么快速检验呢？显然那些最大值小于当前答案的就不用管了，对于那些最大值大于当前答案的，我们必须找到被所有最大值大于当前答案的链覆盖的边，这些边中最大的去减掉链中最大的要是合法即可满足当前答案，如何求上述问题呢？

树上差分：树上差分总结：可以O(1)修改树上路径每条边边权或点权（对每条边相同的修改值），O(n)求出两点间的边权和或点权和。假设修改值为1，即可解决点或边的覆盖链数目。

因此每次二分答案+树上差分判断即可以

的复杂度通过本题。

Note:写这道题时二分还出了问题，假设最后检测的是l == r（也就是mid），那么检测可以就是l，不行就是l+1，和其他的二分还是有区别的。

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#define maxn 300000
#define max(a,b) (a) > (b) ? (a) : (b)
#define min(a,b) (a) < (b) ? (a) : (b)
inline bool check();
int n , m , f[maxn+5][21] , head[maxn+5] , cnt , depth[maxn+5] , s[maxn+5] , lg[maxn+4] , c[maxn+5] , len[maxn+5] , curmax , ans;
struct edge{
    int next , to , dis;
}e[maxn*2+5];
struct Pair{
    int u , v , f , w;
}p[maxn+5];
inline void pre();
void dfs(int x , int fa , int d);
inline int LCA(int x , int y);
inline void add(int from , int to , int dis);
bool solve(int x);//the edge to x is bughole
void getLegal(int x , int fa);
inline bool cmp(Pair a , Pair b){return a.w < b.w;}
int main()
{
    scanf("%d%d",&n,&m);
    int xx , yy , dd;
    for(int i = 1 ; i <= n-1 ; ++i)
    {
        scanf("%d%d%d",&xx,&yy,&dd);
        add(xx,yy,dd);
        add(yy,xx,dd);
    }
    dfs(1,0,0);
    pre();
    // for(int i =  1 ; i <= n ; ++i)
    //     printf("%d ",len[i]);
    for(int i = 1 ; i <= m ; ++i)
    {
        scanf("%d%d",&p[i].u,&p[i].v);
        p[i].f = LCA(p[i].u,p[i].v);
        p[i].w = s[p[i].u] + s[p[i].v] - 2 * s[p[i].f];
        // printf("%d %d %d %d\n",p[i].u,p[i].v,p[i].f,p[i].w);
    }
    std::sort(p+1,p+m+1,cmp);
    // for(int i = 1 ; i <= m ; ++i)
    //     printf("%d\n",p[i].w);
    int l = 0 ,r = maxn*1000;
    while(l <= r)
    {
        int mid = l + r >> 1;
        // printf("l = %d r = %d mid = %d\n",l,r,mid);
        if(solve(mid)) r = mid - 1 ;
        else l = mid + 1;
    }
    printf("%d",max(l,0));
}
void dfs(int x , int fa , int d)
{
    depth[x] = depth[fa] + 1;
    f[x][0] = fa;
    s[x] = s[fa] + d;
    len[x] = d;
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fa)
            dfs(e[i].to,x,e[i].dis);
}
inline int LCA(int x , int y)
{
    if(depth[x] < depth[y])  std:: swap(x,y);
    while(depth[x] > depth[y])
        x = f[x][lg[depth[x]-depth[y]]-1];
    if(x == y) return x;
    for(int i = lg[depth[x]]; i >= 0 ; i--)
        if(f[x][i] != f[y][i])
            x = f[x][i] , y = f[y][i];
    return f[x][0];
 
}
inline void pre()
{
    for(int j = 1 ; j <= 20 ; ++j)
        for(int i = 1 ; i <= n ; ++i)
            f[i][j] = f[f[i][j-1]][j-1];
    for(int i = 1 ; i <= n ; ++i)
          lg[i] = lg[i-1]+(1<<lg[i-1]==i);
}
inline void add(int from , int to , int dis)
{
    e[++cnt].next = head[from];
    e[cnt].to = to;
    e[cnt].dis = dis;
    head[from] = cnt;
}
bool solve(int x)
{
    // printf("the time of = %d\n",x);
    for(int i = 1 ; i <= n ; ++i)// the differ array to find the common edge
        c[i] = 0 ;
    curmax = -99999999;
    int maxx = -99999999;
    int l = 0 , r = m;
    // while(l <= r)
    // {
    //     int mid = l + r >> 1;
    //     if(p[mid].w <= x) l = mid + 1;
    //     else r = mid - 1;
    // }
    // printf("%d %d\n",l,r);
    for(int i = 1 ; i <= n ; ++i)
        if(p[i].w > x)
        {
            l = i;
            break;
        }
    if(!l) return true;
    for(int i = l ; i <= m ; ++i)
        ++c[p[i].u] , ++c[p[i].v] , c[p[i].f] -= 2 , maxx = max(maxx,p[i].w);//tree differ of edge
    getLegal(1,0);
    // if(tot == 0) return false;
    // printf("the num of illigal = %d ",m-l+1);
    // for(int i = 1; i <= n ; ++i)
        // printf("c[%d]=%d ",i,c[i]);
    for(int i = 1 ; i <= n ; ++i)
        if(c[i] == m-l+1)
            curmax = max(curmax,len[i]);
    // printf("curmax = %d , maxx = %d ",curmax,maxx);
    // putchar(10) , putchar(10);
    if(maxx - curmax <= x) return true;
    else return false;
}
void getLegal(int x , int fa)
{
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fa)
            getLegal(e[i].to,x) , c[x] += c[e[i].to];
}

边权差分（仅仅是LCA节点最后少减一个1）

[JLOI2014]松鼠的新家

题目描述

松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在”树“上。

松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，……，最后到an，去参观新家。可是这样会导致维尼重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。

维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。

因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

输入输出格式

输入格式：

第一行一个整数n，表示房间个数第二行n个整数，依次描述a1-an

接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。

输出格式：

一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。

输入输出样例

输入样例#1：

1
2
3
4
5
6
5
1 4 5 3 2
1 2
2 4
2 3
4 5

输出样例#1：

1
2
3
4
5
1
2
1
2
1

说明

2<= n <=300000

注意细节就好.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// luogu-judger-enable-o2
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#define maxn 300000
int n , t[maxn+5] , head[maxn+5] , cnt , c[maxn+5] , f[maxn+5][21] , depth[maxn+5] , lg[maxn+5];
struct edge{
    int next , to;
}e[maxn*2+5];
struct link{
    int u , v , f;
}l[maxn+5];
inline int LCA(int x , int y);
inline void pre();
void dfs(int x , int fa);
inline void add(int from, int to);
void dif();
void getDif(int x , int fa);
inline void swap(int& x , int& y);
int main()
{
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&t[i]);
    for(int i = 1 ; i <= n ; ++i)
        lg[i] = lg[i-1] + (1<<lg[i-1] == i);
    int x , y ;
    for(int i = 1 ; i <= n-1 ; ++i)
        scanf("%d%d",&x,&y) , add(x,y) , add(y,x);
    dfs(1,0);
    pre();
    for(int i = 2 ; i <= n ; ++i)
        l[i-1].u = t[i-1] , l[i-1].v = t[i] , l[i-1].f = LCA(l[i-1].u,l[i-1].v);
    // for(int i = 1 ; i <= n-1 ; ++i)
    //     printf("l[%d].u = %d l[%d].v = %d l[%d].f = %d\n",i,l[i].u,i,l[i].v,i,l[i].f);
    dif();
    for(int i = 1 ; i <= n ; ++i)
        printf("%d\n",c[i]);
}
inline void add(int from, int to)
{
    e[++cnt].next = head[from];
    e[cnt].to = to;
    head[from] = cnt;
}
void dfs(int x , int fa)
{
    depth[x] = depth[fa] + 1;
    f[x][0] = fa;
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fa)
            dfs(e[i].to,x);
}
inline void pre()
{
    for(int j = 1 ; j <= 20 ; ++j)
        for(int i = 1 ; i <= n ; ++i)
            f[i][j] = f[f[i][j-1]][j-1];
}
void dif()
{
    for(int i = 1 ; i <= n-1 ; ++i)
        ++c[l[i].u] , ++c[l[i].v] , --c[l[i].f] , --c[f[l[i].f][0]];
    // ++c[l[n-1].u] , ++c[f[l[n-1].v][0]] , --c[LCA(l[n-1].u,f[l[n-1].v][0])];
    getDif(1,0);
    for(int i = 2 ; i <= n ; ++i)
        --c[t[i]];
}
void getDif(int x, int fa)
{
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fa)
            getDif(e[i].to , x) , c[x] += c[e[i].to];
}
inline int LCA(int x, int y)
{
    if(depth[x] < depth[y]) swap(x,y);
    while(depth[x] > depth[y])
        x = f[x][lg[depth[x]-depth[y]]-1];
    if(x == y) return x;
    for(int i = lg[depth[x]] ; i >= 0 ; --i)
        if(f[x][i] != f[y][i])
            x = f[x][i] , y = f[y][i];
    return f[x][0];
}
inline void swap(int& x, int& y)
{
    int t;
    t = x , x = y , y = t;
}