T1 随（Rand）

T2 单（single）

考场上，简单看一眼就看出是个高斯消元，然后。。。。。

板子没记住！！！

然而这不是最糟糕的。。。。

执着的我进行了对高斯消元的推演与运行，在大把时间荒废后，发现自己终于将样例中的一半答对了！！

然而，考试接近了尾声，匆匆地蒙了下其他几个题的答案就结束了。。。

然而，高斯消元推假了。。。。

就这样达成成就———爆〇！！

其实上，这题做法比较多（部分分数），然而这题的ac代码是dfs。看了题解之后思路清晰展了，很快码完，但想想这题思维量，考上上暂时还做不到呢。。。。。

正确思路：

t=0的时候知道a数组，这时候可以求出所有点到根（1）的距离，这样可以生猛的算出b[1],

接着找（1）和他儿子们的关系，列出表达式发现以儿子（2）为根点的子树上对（2）的距离（称为贡献）都少了1，

于是，我们记录一个size数组表示以i为根节点的子树上的点权和

由于父子间的关系可以推出b[son]=b[fa]+size[1]-2*size[son];

dfs一遍就可以求出b；

t=1时，将上面柿子移项可得b[son]-b[fa]=size[1]-2*size[son]；

插一句嘴，我们可以发现b[1]=size[2]+size[3]+size[4]+…+size[n]

就和之前的那个概率期望的神仙推柿子题一样，将size展开然后合并同类项发现每个点加的次数都为那个点的深度减一，及到根节点距离；

将c[i]=size[1]-2*size[i]; i！=1；

将除了c[1]的c数组加和得： tot=(n-1)size[1]-2*(size[2]+size[3]+…+size[n])

呕吼，可以化简了！！ tot=(n-1)size[1]-2*b[1]；

这样，原本未知的size便可以求了 size[i]=(size[1]-c[i])/2

求出size，将size倒着求a就可以知道a是啥了；

这种思维量大的题不多见，考场上还是要仔细思考，别放过任何一点新奇的想法，才有可能想对吧。。。。

1 #include
2 #define int long long
3 using namespace std;
4 const int NN=1e5+5;
5 int T,n,dis[NN],a[NN],b[NN],size[NN],c[NN];
6 struct SNOW{
7 int to,next;
8 }; SNOW e[NN<<1]; int r[NN<<1],tot; 9 inline void add(int x,int y){ 10 e[++tot]=(SNOW){y,r[x]}; 11 r[x]=tot; 12 } 13 inline void dfs(int fa,int x){ 14 for(int i=r[x];i;i=e[i].next) 15 if(e[i].to!=fa){ 16 dis[e[i].to]=dis[x]+1; 17 dfs(x,e[i].to); 18 } 19 } 20 inline void dfs1(int fa,int x){ 21 for(int i=r[x];i;i=e[i].next) 22 if(e[i].to!=fa){ 23 dfs1(x,e[i].to); 24 size[x]+=size[e[i].to]; 25 } 26 } 27 inline void dfs2(int fa,int x){ 28 for(int i=r[x];i;i=e[i].next) 29 if(e[i].to!=fa){ 30 b[e[i].to]=b[x]+size[1]-2*size[e[i].to]; 31 dfs2(x,e[i].to); 32 } 33 } 34 inline void dfs3(int fa,int x){ 35 for(int i=r[x];i;i=e[i].next) 36 if(e[i].to!=fa){ 37 c[e[i].to]=a[e[i].to]-a[x]; 38 dfs3(x,e[i].to); 39 } 40 } 41 inline void dfs4(int fa,int x){ 42 for(int i=r[x];i;i=e[i].next) 43 if(e[i].to!=fa){ 44 b[e[i].to]=size[e[i].to]=(size[1]-c[e[i].to])/2; 45 dfs4(x,e[i].to); 46 } 47 } 48 inline void dfs5(int fa,int x){ 49 for(int i=r[x];i;i=e[i].next) 50 if(e[i].to!=fa){ 51 dfs5(x,e[i].to); 52 b[x]-=size[e[i].to]; 53 } 54 } 55 inline int read(){ 56 int x=0,f=1; char ch=getchar(); 57 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
58 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
59 return x*f;
60 }
61 namespace WSN{
62 inline int main(){
63 T=read();
64 while(T--){
65 memset(b,0,sizeof(b));
66 memset(c,0,sizeof(c));
67 memset(size,0,sizeof(size));
68 memset(dis,0,sizeof(dis));
69 memset(r,0,sizeof(r)); tot=0;
70 n=read();
71 for(int i=1;i<n;i++){
72 int x=read(),y=read();
73 add(x,y); add(y,x);
74 }
75 int t=read();
76 for(int i=1;i<=n;i++) a[i]=read();
77 if(!t){
78 dfs(0,1);
79 for(int i=2;i<=n;i++) b[1]+=dis[i]*a[i];
80 for(int i=1;i<=n;i++) size[i]=a[i];
81 dfs1(0,1);
82 dfs2(0,1);
83 for(int i=1;i<=n;i++) printf("%lld ",b[i]);
84 putchar('\n');
85 }
86 if(t){
87 dfs3(0,1); int cnt=0;
88 for(int i=2;i<=n;i++) cnt+=c[i];
89 size[1]=(cnt+2*a[1])/(n-1);
90 dfs4(0,1);
91 dfs5(0,1);
92 b[1]=size[1];
93 for(int i=2;i<=n;i++) b[1]-=b[i];
94 for(int i=1;i<=n;i++) printf("%lld ",b[i]);
95 putchar('\n');
96 }
97 }
98 return 0;
99 }
100 }
101 signed main(){return WSN::main();}

然而，六个dfs就很淦，感觉打完这道题对xin_team的理解又加深了不少呢

T3 题（problem）

这题就是相当于考了一个卡特兰数，然而我们这一批人还没学。。。

怎么办呢？那就学呗

大佬传送门

t=0，枚举向横向移动步数，必须是偶数，则纵向步数n-i。

从中选1/2向正方向走，另一半反向走C(n,i)_C(i,i/2)_C((n-i),(n-i)/2)

t=1，卡特兰数公式走起即可catalan(n)=C(2n,n)/(n+1)，至于有一个奇怪的错误就是另一个表达式他用了会错，不明白为什么

t=2，使用dp，注意是四个方向

            f[0]=1;
            for(int i=0;i<=n;i+=2){
                for(int j=0;j<=i;j+=2){
                    f[i]=(f[i]+f[i-j]*4%p*catlan(j/2-1)%p)%p;
                }

t=3，数据累加加卡特兰数，思路较简单（当时重点不知道卡特兰数是啥，汗）

1 #include
2 #define int long long
3 using namespace std;
4 const int p=1e9+7;
5 int hi[3000000],n,typ;
6 inline int jie(int x){
7 if(x==1||x==0) return 1;
8 if(hi[x]) return hi[x];
9 return hi[x]=((jie(x-1)%p)*(x%p))%p;
10 }
11 inline int fima(int a){
12 int ans=1,b=p-2; a=a%p;
13 while(b){
14 if(b&1) ans=(ans*a)%p;
15 b>>=1,a=(a*a)%p;
16 } return ans;
17 }
18 inline int C(int n,int m){
19 if(n==m) return 1;
20 return jie(n)*fima(jie(m)*jie(n-m)%p)%p;
21 }
22 inline int catlan(int n){
23 return C(2*n,n)*fima(n+1)%p;
24 }
25 inline int read(){
26 int x=0,f=1; char ch=getchar();
27 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
28 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
29 return x*f;
30 }
31 namespace WSN{
32 inline int main(){
33 n=read(),typ=read();
34 if(typ==1) printf("%lld\n",catlan(n/2));
35 if(typ==0){
36 int ans=0;
37 for(int i=0;i<=n;i++)
38 if(!(i&1)) ans=(ans+C(n,i)*C(i,i/2)%p*C((n-i),(n-i)/2)%p)%p;
39 printf("%lld\n",ans);
40 }
41 if(typ==3){
42 int ans=0;
43 for(int i=0;i<=n;i++)
44 if(!(i&1)) ans=(ans+C(n,i)*catlan(i/2)%p*catlan((n-i)/2)%p)%p;
45 printf("%lld\n",ans);
46 }
47 if(typ==2){
48 int f[1005]={};
49 f[0]=1;
50 for(int i=0;i<=n;i+=2){
51 for(int j=0;j<=i;j+=2){
52 f[i]=(f[i]+f[i-j]*4%p*catlan(j/2-1)%p)%p;
53 }
54 }
55 printf("%lld\n",f[n]);
56 }
57 return 0;
58 }
59 }
60 signed main(){return WSN::main();}