NOIP 模拟4 T2

本题属于二和一问题子问题相互对称

考虑对于问题一：知a求b

　　那么根据b数组定义式显然能发现问题在于如何求dis（最短路）

　　有很多算法可供选择 dijsktra,floyed,bfs/dfs,spfa等

　　然而我们发现本题一个特点为边权相等（1）显然应用dfs/bfs算法时间复杂度优于传统求最短路算法

考虑对于问题二：知b求a

　　同样，我们能很快明确高斯消元算法并且也需要计算dis数组

然而观察数据范围 T<=5, 2<=n<=100000,1<=u,v<=n

　　显然这道题正解并不是高斯消元与最短路算法因为空间与时间复杂度完全不可能（将dis数组转为一维对于问题一能解决dis数组空间限制然而对于其余关键算法无能为力）

那么在考场上正确的策略显然是对暴力求法进行优化而不是一味追求正解顺着这个思路继续思考

考虑对于问题一：

　　算法瓶颈在于求解最短路的时间空间问题分析数据范围我们发现至少复杂度要降低一个维度才可行

　　这启发我们利用递推方式求解加之以本题是树形结构思路就逐渐明了:二次扫描与换根法（对于NOIP模拟级习题本算法显然不必多讲）

　　那么思维方向已现考虑节点转移对于b数组的影响可推出 b[node[i].to] = b[from] + sum_w - w[node[i].to] * 2（其中w[i]代表已i为跟节点子树sigma（a））依次优化复杂度

考虑对于问题二：

　　尽管高斯消元不可行但问题本质仍然为对b[i]的求解也就是说同样需要消元求解

　　问题一的解法启发我们问题二应该也与树形结构有关

　　类比问题一我们考虑节点转移对a数组的影响很容易得出 b[node[i].to] - b[from] = sum_w - w[node[i].to] * 2;

　　至此我们推出了将b[2]~b[n]与w[2]~w[n]联系在一起的式子很容易想到要求b[1]与这些量之间的关系易得 b[1] = sigma(w[i]) （i！=1）

　　显然连接纽带在于w数组初等变换得 sigma(b[node[i].to - b[from]) = (n - 1)*sum_w - 2*sigma(w[i]) 代入b[1]得 sigma(b[node[i],to - b[from]]) + 2*b[1] = (n - 1)*sum_w;

　　代入求得sum_w 在将sum_w代回原式可解出w[i]

　　根据w[i]的定义可知求解a数组只需要对w数组做差分即可

　　代码如下（主要是思路代码无难度建议练习）

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define I int

  4 #define LL long long

  5 #define B bool

  6 #define C char

  7 #define RE register

  8 #define V void

  9 #define L inline

 10

 11 const I MAXN = 100010;

 12 I T,t,x,y,n;

 13 LL a[MAXN],b[MAXN],sum[MAXN];

 14 I num,head[MAXN];

 15 LL SUM;

 16 B jud[MAXN];

 17 struct LYM

 18 {

 19         I to,next;

 20 }node[MAXN << 1];

 21 L I read();    L V store(I,I);

 22 V dfs1(I);    V dfs2(I);    V dfs3(I);    V dfs4(I);

 23 signed main()

 24 {

 25         T = read();

 26         while(T -- ){

 27             n = read();

 28             for(RE I i(1);i < n; ++ i){

 29                     x = read(),y = read();

 30                     store(x,y),store(y,x);

 31             }

 32             t = read();

 33             if(t)

 34             {

 35                     for(RE I i(1);i <= n; ++ i)    b[i] = read();

 36                     dfs3(1);    SUM += b[1] * 2;    SUM /= n - 1;

 37                     sum[1] = SUM;       dfs4(1);

 38                     for(RE I i(1);i <= n; ++ i)    printf("%lld ",a[i]);

 39             }

 40             else

 41             {

 42                     for(RE I i(1);i <= n; ++ i)    a[i] = read();

 43                     dfs1(1);

 44                     for(RE I i(2);i <= n; ++ i)    b[1] += sum[i];

 45                     dfs2(1);

 46                     for(RE I i(1);i <= n; ++ i)    printf("%lld ",b[i]);

 47             }

 48             printf("\n");

 49             num = 0,SUM = 0;

 50             memset(head,0,sizeof(head));

 51             memset(sum,0,sizeof(sum));

 52             memset(a,0,sizeof(a));

 53             memset(b,0,sizeof(b));

 54         }

 55 }

 56 L I read()

 57 {

 58         RE I x(0),y(1); RE C z = getchar();

 59         while(!isdigit(z))      y |= z == '-',z = getchar();

 60         while(isdigit(z))       x = (x << 3) + (x << 1) + (z ^ 48),z = getchar();

 61         return x * y;

 62 }

 63 L V store(I from,I to)

 64 {

 65         node[++num].to = to;

 66         node[num].next = head[from];

 67         head[from] = num;

 68 }

 69 V dfs1(I from){

 70         jud[from] = 1;

 71         sum[from] += a[from];

 72         for(RE I i(head[from]); i ;i = node[i].next){

 73             if(!jud[node[i].to]){

 74                 dfs1(node[i].to);

 75                 sum[from] += sum[node[i].to];

 76             }

 77         }

 78         jud[from] = 0;

 79 }

 80 V dfs2(I from){

 81         jud[from] = 1;

 82         for(RE I i(head[from]); i ;i = node[i].next){

 83             if(!jud[node[i].to]){

 84                 b[node[i].to] = b[from] + sum[1] - (sum[node[i].to] << 1);

 85                 dfs2(node[i].to);

 86             }

 87         }

 88         jud[from] = 0;

 89 }

 90 V dfs3(I from){

 91         jud[from] = 1;

 92         for(RE I i(head[from]); i ;i = node[i].next){

 93             if(!jud[node[i].to]){

 94                 SUM += b[node[i].to] - b[from];

 95                 dfs3(node[i].to);

 96             }

 97         }

 98         jud[from] = 0;

 99 }

100 V dfs4(I from){

101         jud[from] = 1;

102         LL tool = sum[from];

103         for(RE I i(head[from]); i ;i = node[i].next){

104             if(!jud[node[i].to]){

105                 sum[node[i].to] = (SUM - b[node[i].to] + b[from]) >> 1;

106                 dfs4(node[i].to);

107                 tool -= sum[node[i].to];

108             }

109         }

110         a[from] = tool;

111         jud[from] = 0;

112 }

巴特西

NOIP 模拟4 T2

最新文章

热门文章