hzoj NOI 模拟题单

2024-03-28 21:38:28

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 现役

码农公寓