hzoj NOI 模拟题 单

Description:

题目描述:

  单车联通大街小巷.这就是出题人没有写题目背景的原因.
  对于一棵树,认为每条边长度为1,每个点有一个权值a[i].dis(u,v)为点u到v的最短路径的边数.dis(u,u)=0.对每个点求出一个重要程度.点x的重要程度b[x]定义为其他点到这个点的距离乘上对应的点权再求和. 即:b[x]=a[1]dis(1,x)+a[2]dis(2,x)+....+a[n]*dis(n,x)
现在有很多树和对应的a数组,并求出了b数组.不幸的是,记录变得模糊不清了.幸运的是,树的形态完好地保存了下来,a数组和b数组至少有一个是完好无损的,但另一个数组完全看不清了.希望你求出受损的数组.多组数据.

输入格式:

  第一行输入一个T,表示数据组数。接下来T组数据。
  每组数据的第1行1个整数n表示树的点数.节点从1到n编号.
  接下来n-1行每行两个整数u,v表示u和v之间有一条边.
  接下来一行一个整数t,表示接下来数组的类型。
  t=0则下一行是a数组,t=1则下一行是b数组。
  接下来一行n个整数,表示保存完好的那个数组,第i个数表示a[i]或b[i]。

输出格式:

  T行,每组数据输出一行表示对应的a数组或b数组,数组的相邻元素用一个空格隔开。忽略行末空格和行尾回车。

样例:

样例输入:

2
2
1 2
1
17 31
2
1 2
0
31 17

样例输出

31 17
17 31

数据范围与提示

  对于100%的数据,T=5, 2<=n<=100000,1<=u,v<=n,保证给出的n-1条边形成一棵树
  对于100%的数据,t=0或t=1,1<=a[i]<=100,1<=b[i]<=10^9,t=1时保证给出的b数组对应唯一的一个a数组。
  对于100%的数据,单个输入文件不会包含超过2000000个整数,这段话可以理解为,你不必考虑输入输出对程序运行时间的影响。
  对于100%的数据,保证答案不会超过int能表示的范围
  接下来描述了每个测试点的具体特征。每个测试点的5组数据均符合表格中对应的特征
  1:n<=1000,均有t=0;
  2:n<=5,均有t=1,答案中a[i]<=20;
  3,4:n<=100,均有t=1;
  5:n<=30000,所有边满足v=u+1;
  6,7:n<=10^5,均有t=0;
  8,9,10:n<=10^5,无限制

思路:

  很明显,这题要递推,我们可以找到儿子与父亲间的关系来,然后跑DFS递推即可,复杂度在O(n);
  我们先画一棵树(假装作者已经画了一棵树),然后我们会发现,从儿子转换到父亲,会有:

b[fa]=b[son]+sum[son]-(SUM-sum[son]);其中sum表示以son为根的子树里所有点(包括son本身)的a的和,SUM为整棵树上所有点的a的和

  这是因为,从儿子到父亲,经历了一条边,使得subtree(son)上所有的点的dis延伸了1,因此要加上sum[son],且使得除了subtree(son)上的点的所有点的dis缩短了1,这是整道题里最关键的式子。,然后对t=1与t=0分别考虑
  首先考虑t=0的情况。很明显,我们可以先O(n)的效率累加sumi从而求出b[1],然后跑dfs根据上面的式子递推即可,SUM即为sum[1]。
  考虑t=1的情况,我们可以知道b[1]=sigma(sum[i])(i=2~n),回顾刚才那个式子,我们可以把它变形为:

SUM-2*sum[son]=num[son],num[son]=b[son]-b[fa];

  我们可以先dfs一遍,求出num来。然后相加,就会发现,如果将2提出,括号里的即为b[1],就有:

(n-1)SUM-2b[1]=sigma(num[i])(i=2~n);

  然后SUM(sum[1])可求,又有:

sum[now]=sigma(sum[son])+a[now];

  然后你要干啥就不用我说了吧。。。这个可以用dfs实现。

上代码:

#include<bits/stdc++.h>
using namespace std;
namespace Decleration{
    #define ll long long 
    #define rr register 
    const int SIZE=1e5+4;    
    int T,n,t;
    ll num[SIZE],sum[SIZE];
    ll a[SIZE],b[SIZE];
    vector<int> chil[SIZE];
    ll read(){
        rr ll x_read=0,y_read=1;
        rr char c_read=getchar();
        while(c_read<'0'||c_read>'9'){
            if(c_read=='-') y_read=-1;
            c_read=getchar();}
        while(c_read<='9'&&c_read>='0'){
            x_read=(x_read<<3)+(x_read<<1)+(c_read^48);
            c_read=getchar();}
        return x_read*y_read;}
    void Pre_Deal(){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(sum,0,sizeof(sum));
        memset(num,0,sizeof(num));
        for(rr int i=1;i<=n;i++) chil[i].clear();}
    //求a:
    void dfs_A1(int now,int fa){
        if(now!=1) num[now]=b[now]-b[fa];
        for(int i=0;i<chil[now].size();i++)
            if(chil[now][i]!=fa) dfs_A1(chil[now][i],now);}
    void dfs_A2(int now,int fa){
        ll temp=0;
        for(int i=0;i<chil[now].size();i++)
            if(chil[now][i]!=fa){
                temp+=sum[chil[now][i]];
                dfs_A2(chil[now][i],now);}
        a[now]=sum[now]-temp;}
    void A(){
        for(rr int i=1;i<=n;i++) b[i]=read();
        dfs_A1(1,1);
        ll temp=0;
        //num[i]==SUM-2*sum[i]
        for(rr int i=2;i<=n;i++) temp+=num[i];//->(n-1)*SUM-2*sigma(sum[i])->(n-1)*SUM-2*b[1]
        sum[1]=(temp+2*b[1])/(n-1);
        for(rr int i=2;i<=n;i++) sum[i]=(sum[1]-num[i])>>1;
        dfs_A2(1,1);
        for(rr int i=1;i<=n;i++) printf("%lld ",a[i]);
        printf("\n");}
    //求b:
    void dfs_B1(int now,int fa){
        for(int i=0;i<chil[now].size();i++)
            if(chil[now][i]!=fa){
                dfs_B1(chil[now][i],now);
                sum[now]+=sum[chil[now][i]];}
        sum[now]+=a[now];
        if(now!=1)
          b[1]+=sum[now];}
    void dfs_B2(int now,int fa){
        if(now!=1) b[now]=b[fa]+sum[1]-(sum[now]<<1);
        for(int i=0;i<chil[now].size();i++)
            if(chil[now][i]!=fa)
                dfs_B2(chil[now][i],now);}
    void B(){
        for(rr int i=1;i<=n;i++) a[i]=read();
        dfs_B1(1,1);
        dfs_B2(1,1);
        for(rr int i=1;i<=n;i++) printf("%lld ",b[i]);
        printf("\n");}
};
using namespace Decleration;
int main(){
    T=read();
    while(T--){
        n=read();
        Pre_Deal();        
        for(rr int i=1;i<n;i++){
            int u=read(),v=read();
            chil[v].push_back(u);
            chil[u].push_back(v);}
        t=read();
        if(t) A();
        else B();}}

写在最后的话:

  自己在考试的时候独立想出的求b的算法,与上文中的不同,上文给出的是优化算法。考试时自己想出了num的表达式,但不会用,所以求a的算法考试时并没有想出来。
  看题解时,题解中的一句话让我很受震动,他说数据5是给人以启发的,其实考试时也意识到了,但没有细想,只是灵光一闪,转瞬即逝,以后再次碰到时就不可放弃了。
2021.6.6 现役

上一篇:[Android逆向]超级录屏 4.3.1.8_rel 高级版解锁


下一篇:Mac下搭建solr搜索引擎与PHP扩展开发(下)