详解斯坦纳点及斯坦纳树及模版归纳总结

①什么是斯坦纳点?

  假设原来已经给定了个点,库朗等指出需要引进的点数至多为,此种点称为斯坦纳点。过每一斯坦纳点,至多有三条边通过。若为三条边,则它们两两交成120°角;若为两条边,则此斯坦纳点必为某一已给定的点,且此两条边交成的角必大于或等于120°。其中最小的网络称为已给定点的集合的最小斯坦纳树,记作SMT。若此SMT的斯坦纳点中有等于给定点的点,则称此SMT为退化的,此给定点称为退化点。

构造方法:

已知B,C,D,E可知B点为转轴线段BC绕B顺时针旋转60度得到正三角形,再以顶点F为转轴,FD构成的线段逆时针旋转得到新的正三角形顶点G,劣弧DF上任意一点都能和D,F构成三个,相同的,劣弧CB上的点也是。

故将第四点E与G相连接在劣弧上得到一个交点,再由交点与F连接交劣弧CB于一点,即构成了非退化情况下的两斯坦纳点,枚举得到斯坦纳最小生成树,当与顶点连线不与劣弧有交点时则为该种结构的退化点情况.

②什么是斯坦纳树?

       斯坦纳树问题是组合优化学科中的一个问题。将指定点集合中的所有点连通,且边权总和最小的生成树称为最小斯坦纳树(Minimal Steiner Tree),其实最小生成树是最小斯坦纳树的一种特殊情况。而斯坦纳树可以理解为使得指定集合中的点连通的树,但不一定最小。

③如何求解最小斯坦纳树?

      可以用DP求解,dp[i][state]表示以i为根,指定集合中的点的连通状态为state的生成树的最小总权值。

      转移方程有两重:

      第一重,先通过连通状态的子集进行转移。

      dp[i][state]=min{ dp[i][subset1]+dp[i][subset2] } 

      枚举子集的技巧可以用 for(sub=(state-1)&state;sub;sub=(sub-1)&state)。

      第二重,在当前枚举的连通状态下,对该连通状态进行松弛操作。

      dp[i][state]=min{ dp[i][state], dp[j][state]+e[i][j] }

      为什么只需对该连通状态进行松弛?因为更后面的连通状态会由先前的连通状态通过第一重转移得到,所以无需对别的连通状态松弛。松弛操作用SPFA即可。

      复杂度 O(n*3^k+cE*2^k)

      c为SPFA复杂度中的常数,E为边的数量,但几乎达不到全部边的数量,甚至非常小。3^k来自于子集的转移sum{C(i,n)*2^i} (1<=i<=n),用二项式展开求一下和。

模版如下:

 1 /*
 2  *  Steiner Tree:求,使得指定K个点连通的生成树的最小总权值
 3  *  st[i] 表示顶点i的标记值,如果i是指定集合内第m(0<=m<K)个点,则st[i]=1<<m 
 4  *  endSt=1<<K
 5  *  dptree[i][state] 表示以i为根,连通状态为state的生成树值
 6  */
 7 #define CLR(x,a) memset(x,a,sizeof(x))
 8 
 9 int dptree[N][1<<K],st[N],endSt;
10 bool vis[N][1<<K];
11 queue<int> que;
12 
13 int input()
14 {
15    /*
16     *    输入,并且返回指定集合元素个数K
17     *    因为有时候元素个数需要通过输入数据处理出来,所以单独开个输入函数。
18     */
19 }
20 
21 void initSteinerTree()
22 {
23     CLR(dptree,-1);
24     CLR(st,0);
25     for(int i=1;i<=n;i++) CLR(vis[i],0);
26     endSt=1<<input();
27     for(int i=1;i<=n;i++)
28         dptree[i][st[i]]=0;
29 }
30 
31 void update(int &a,int x)
32 {
33     a=(a>x || a==-1)? x : a;
34 }
35 
36 void SPFA(int state)
37 {
38     while(!que.empty()){
39         int u=que.front();
40         que.pop();
41         vis[u][state]=false;
42         for(int i=p[u];i!=-1;i=e[i].next){
43             int v=e[i].vid;
44             if(dptree[v][st[v]|state]==-1 || 
45                 dptree[v][st[v]|state]>dptree[u][state]+e[i].w){
46 
47                 dptree[v][st[v]|state]=dptree[u][state]+e[i].w;
48                 if(st[v]|state!=state || vis[v][state]) 
49                     continue; //只更新当前连通状态
50                 vis[v][state]=true;
51                 que.push(v);
52             }
53         }
54     }
55 }
56 
57 void steinerTree()
58 {
59     for(int j=1;j<endSt;j++){
60         for(int i=1;i<=n;i++){
61             if(st[i] && (st[i]&j)==0) continue;
62             for(int sub=(j-1)&j;sub;sub=(sub-1)&j){
63                 int x=st[i]|sub,y=st[i]|(j-sub);
64                 if(dptree[i][x]!=-1 && dptree[i][y]!=-1)
65                     update(dptree[i][j],dptree[i][x]+dptree[i][y]);
66             }
67             if(dptree[i][j]!=-1) 
68                 que.push(i),vis[i][j]=true;
69         }
70         SPFA(j);
71     }
72 }

④学习心得

  参考09年姜碧野神牛写的论文《SPFA的优化与应用》,里面提到了一道题——[WC2008]游览计划。这题让我立刻联想到了去年北京赛区的E题,差不多的模型,大概就是在一个图中求给定的k个点的斯坦纳生成树,给定点的个数k<=10。

       首先我们知道,最优解必然是一棵树,然后这棵树又是由若干棵子树合并成的,于是我们可以状态压缩,把k个节点的连通状态用一个二进制数j表示,dp[i][j]表示以i为根和对应状态为j的节点连通的子树的最小权值。有两种转移方法:

       枚举子树的形态:dp[ i ][ j ]=min{ dp[ i ][ j ],dp[ i ][ k ]+dp[ i ][ l ] },其中k和l是对j的一个划分。

       按照边进行松弛:dp[ i ][ j ]=min{ dp[ i ][ j ],dp[ i' ][ j ]+w[ i ][ i' ] },其中i和i'之间有边相连。

       对于第一种转移,我们直接枚举子集就行了。对于第二种转移,我们仔细观察可以发现这个方程和最短路的约束条件是很类似的,于是我们可以用spfa或者dij来进行状态转移。枚举子集的复杂度=n*sum{C(k,i)*2^i,0<i=k}=n*3^k,spfa的复杂度为n*2^k。所以总复杂度为O(n*3^k)。

       具体实现的时候我试了好几种不同的方法,一开始是直接把两种转移都看成图中的边,一遍spfa得出结果,大概如下所示:

 1 void spfa(){
 2     while(!Q.empty()){
 3         int x=Q.front()/10000,y=Q.front()%10000;
 4         in[x][y]=0;
 5         Q.pop();
 6         for(edge *i=Adj[x];i;i=i->nxt)       //对当前节点的每条边都进行松弛操作
 7             update(i->v,s[i->v]|y,d[x][y]+i->w);
 8         int t=nn-1-y;
 9         for(int i=t;i;i=(i-1)&t)            //枚举补集的所有子集,进行松弛操作
10             update(x,y|i,d[x][y]+d[x][i|s[x]]);
11     }
12 }

     这么做的复杂度是没有变的,但是常数非常大,hdu上跑了2500ms才过,仔细一想,我们发现第二松弛操作其实做了很多无用功,考虑能不能进行优化。

       第二种松弛操作非常的耗时间,所以我们就不把它加到spfa里面进行转移,直接在外面进行枚举,实现更新,避免大量的重复计算。先枚举连通性j,对于所有的1<=i<=n,我们先进行第一种转移,既枚举子集进行更新。如果dp[i][j]被更新了,我们就把它加到队列里,最后再进行spfa(),这样按j分层的进行转移,大概如下:

1 for(int y=0;y<nn;y++)                             //枚举连通性
2             for(int x=1;x<=n;x++){
3                 bool flag=0;
4                 for(int i=(y-1)&y;i;i=(i-1)&y)      //枚举所有子集,进行第一种转移
5                     flag|=update(x,y,d[x][i|s[x]]+d[x][(y-i)|s[x]]);
6                 if(flag) Q.push(x*10000+y);       //如果节点被更新则加入队列
7                 spfa();       //spfa进行第二种转移
8             }

       我本来以为这样会更快一些,结果跑了4700ms = =!顿时吐槽无力。

       为啥这样会更慢呢?我觉的大概是由于spfa()的次数过多,所以导致很多节点被重复的更新了很多次,又产生了大量了重复计算,所以反而更慢了。那么就没有什么好办法吗?仔细一想,我发现进行spfa的时候只需要对当前层的节点进行spfa就行了,不需要整个图完全松弛一遍,因为更高的层都可以通过枚举子集而变成若干个更低的层,这样一次spfa的复杂度一下就降了下来,变成了O(n)级别,大概如下:

1 for(edge *i=Adj[x];i;i=i->nxt)
2     if(update(i->v,y|s[i->v],d[x][y]+i->w)&&y==(y|s[i->v])&&!in[i->v][y]) //只把处于相同层的节点加到队列中
3         in[i->v][y]=1,Q.push(i->v*10000+y); 

这样修改以后效果果然非常明显,1000ms就AC了。但还是不够快,别人最快的能够达到500ms。于是我baidu了一下,发现他们没有用spfa!大概就是把第二种转移表示成了另外一种形式:

       dp[ i ][ j ]=min{ dp[ i ][ j ] , dp[ k ][ j ]+d[ k ][ i ] },其中d[ k ][ i ]表示k到i的最短路。

       很容易就能证明这样写方程也是对的,于是我们就可以先用floyed预处理出任意两点间的最短路,然后直接DP。这样做的总复杂度为O(n^3+n^2*2^k+n*3^k),这个复杂度并不比上面的方法低,但由于hdu4085的n比较小,所以这样写反而比上一种方法要快上不少。但对于 [WC2008]游览计划、ZOJ 3613 Wormhole Transport这两道题就不行了,n都达到了100甚至200的大小,这种方法要比前面一种慢。所以最后得出结论,还是前一种方法最稳定 = ^ =

⑤更多习题分享

HDU 4085 Peach Blossom Spring

       11年北京赛区的E题,这题有点不同的地方在于,最后的答案可能是一个森林,所以我们要先求出斯坦纳树后进行DP。转移的时候要注意一点,只有人的个数和房子的个数相等的时候才算合法状态,所以我们要加一个check()函数进行检查。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 #include<queue>
 5 #include<algorithm>
 6 #define N 60
 7 #define INF 2000000
 8 using namespace std;
 9 struct edge{
10     int v,w;
11     edge *nxt;
12 }E[2009],*Adj[N],*cur;
13 int n,m,K,nn;
14 int s[N],in[N][1<<10];
15 int d[N][1<<10],dp[1<<10];
16 queue<int> Q;
17 void addedge(int u,int v,int w){cur->v=v,cur->w=w,cur->nxt=Adj[u],Adj[u]=cur++;}
18 bool check(int x){
19     int r=0;
20     for(int i=0;x;i++,x>>=1)
21         r+=(x&1)*(i<K?1:-1);
22     return r==0;
23 }
24 inline bool update(int x,int y,int w){
25     if(w<d[x][y]) return d[x][y]=w,true;
26     return false;
27 }
28 void spfa(){
29     while(!Q.empty()){
30         int x=Q.front()/10000,y=Q.front()%10000;
31         in[x][y]=0;
32         Q.pop();
33         for(edge *i=Adj[x];i;i=i->nxt)
34             if(update(i->v,y|s[i->v],d[x][y]+i->w)&&y==(y|s[i->v])&&!in[i->v][y])
35                 in[i->v][y]=1,Q.push(i->v*10000+y);
36                 
37     }
38 }
39 void init(){
40     cur=E;
41     memset(Adj,0,sizeof(Adj));
42     memset(s,0,sizeof(s));    
43     scanf("%d%d%d",&n,&m,&K);
44     nn=1<<(2*K);
45     for(int i=1;i<=n;i++)
46         for(int j=0;j<nn;j++)
47             d[i][j]=INF;
48     while(m--){
49         int u,v,w;
50         scanf("%d%d%d",&u,&v,&w);
51         addedge(u,v,w);
52         addedge(v,u,w);
53     }    
54     for(int i=1;i<=K;i++){
55         s[i]=1<<(i-1),d[i][s[i]]=0;                
56         s[n-i+1]=1<<(K+i-1),d[n-i+1][s[n-i+1]]=0;        
57     }    
58 }
59 int main(){    
60     int T;
61     scanf("%d",&T);
62     while(T--){        
63         init();
64         for(int y=0;y<nn;y++){
65             for(int x=1;x<=n;x++){                
66                 for(int i=(y-1)&y;i;i=(i-1)&y)
67                     d[x][y]=min(d[x][y],d[x][i|s[x]]+d[x][(y-i)|s[x]]);
68                 if(d[x][y]<INF) Q.push(x*10000+y),in[x][y]=1;
69             }
70             spfa();
71         }
72         for(int j=0;j<nn;j++){
73             dp[j]=INF;
74             for(int i=1;i<=n;i++) dp[j]=min(dp[j],d[i][j]);
75         }
76         for(int i=1;i<nn;i++)
77             if(check(i))
78                 for(int j=i&(i-1);j;j=(j-1)&i)
79                     if(check(j))
80                         dp[i]=min(dp[i],dp[j]+dp[i-j]);
81         if(dp[nn-1]>=INF) puts("No solution");
82         else printf("%d\n",dp[nn-1]);
83     }
84 }

[WC2008]游览计划

       这题要求一棵满足要求的斯坦纳树,基本上按照上面的做法写就行了,不过有一点恶心的就是要输出一组可行方案,所以DP的时候还要记录一下路径。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 #include<queue>
 5 #include<algorithm>
 6 #define INF 2000000
 7 #define N 10
 8 using namespace std;
 9 int dx[]={0,1,0,-1},
10     dy[]={1,0,-1,0};
11 int max_s,n,m;
12 int mat[N][N],st[N][N],vis[N][N],cnt;
13 int d[N][N][1<<N],pre[N][N][1<<N];
14 bool in[N][N][1<<N];
15 queue<int> Q;
16 void spfa(){
17     int x,y,s,tx,ty,ts;
18     while(!Q.empty()){
19         x=Q.front()/100000;
20         y=(Q.front()-x*100000)/10000;
21         s=Q.front()-x*100000-y*10000;
22         Q.pop();
23         in[x][y][s]=0;
24         for(int i=0;i<4;i++){
25             tx=x+dx[i],ty=y+dy[i];
26             if(tx>=n||ty>=m||tx<0||ty<0) continue;
27             ts=s|st[tx][ty];
28             if(d[x][y][s]+mat[tx][ty]<d[tx][ty][ts]){
29                 d[tx][ty][ts]=d[x][y][s]+mat[tx][ty];
30                 pre[tx][ty][ts]=x*100000+y*10000+s;
31                 if(!in[tx][ty][ts]&&s==ts) in[tx][ty][ts]=1,Q.push(tx*100000+ty*10000+ts);
32             }                
33         }
34     }
35 }
36 void go(int x,int y,int s){
37     vis[x][y]=1;
38     int t=pre[x][y][s],tx,ty,ts;
39     if(!t) return;
40     tx=t/100000;
41     ty=(t-tx*100000)/10000;
42     ts=t-tx*100000-ty*10000;
43     go(tx,ty,ts);
44     if(x==tx&&y==ty) go(x,y,(s-ts)|st[x][y]);
45 }
46 int main(){
47     //freopen("in.in","r",stdin);
48     scanf("%d%d",&n,&m);    
49     for(int i=0;i<n;i++)
50         for(int j=0;j<m;j++){
51             scanf("%d",&mat[i][j]);
52             if(!mat[i][j]) st[i][j]=1<<(cnt++);
53         }    
54     max_s=1<<cnt;
55     for(int i=0;i<n;i++)
56         for(int j=0;j<m;j++){
57             for(int k=0;k<max_s;k++)
58                 d[i][j][k]=INF;
59             if(st[i][j]) d[i][j][st[i][j]]=0;
60         }
61     for(int k=1;k<max_s;k++){
62         for(int i=0;i<n;i++)
63             for(int j=0;j<m;j++){
64                 if(st[i][j]&&!(st[i][j]&k)) continue;                
65                 for(int x=(k-1)&k;x;x=(x-1)&k){
66                     int t=d[i][j][x|st[i][j]]+d[i][j][(k-x)|st[i][j]]-mat[i][j];
67                     if(t<d[i][j][k]) d[i][j][k]=t,pre[i][j][k]=i*100000+j*10000+(x|st[i][j]);
68                 }
69                 if(d[i][j][k]<INF) Q.push(i*100000+j*10000+k),in[i][j][k]=1;
70             }
71         spfa();
72     }
73     for(int i=0;i<n;i++)
74         for(int j=0;j<m;j++)
75             if(st[i][j]){
76                 printf("%d\n",d[i][j][max_s-1]);
77                 go(i,j,max_s-1);
78                 for(int x=0;x<n;x++){
79                     for(int y=0;y<m;y++){
80                         if(st[x][y]) putchar('x');
81                         else if(vis[x][y]) putchar('o');
82                         else putchar('_');
83                     }
84                     puts("");
85                 }
86                 return 0;
87             }
88 }

ZOJ 3613 Wormhole Transport

       ZOJ Monthly, June 2012的C题。和HDU 4085差不多,有一点不同的是一个星球可能有很多个工厂,但是含有资源和含有工厂的星球个数都不超过4。还是先状态压缩,然后DP求出斯坦纳树。最优的方案有可能是森林,所以我们还要DP,dp[ i ]表示对应的工厂节点和资源节点组成的斯坦树森林的最优值。那么:

       dp[ i ]=min{ dp[ i ],dp[ j ]+dp[ k ] },其中j和k为i的一个划分。

       这里要注意一点,所有的状态i、j、k都要满足一个条件,就是连通的星球上工厂的个数要大于等于资源的个数,这样才是一个合法的状态,所以要加一个check()函数。最后再找到所含资源最多,花费最小的合法方案就是答案。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<vector>
 5 #include<algorithm>
 6 #define N 209
 7 using namespace std;
 8 
 9 struct edge{int v,w;edge *nxt;}E[10009],*Adj[N],*cur;
10 int n,m,nn;
11 int d[N][1<<8],dp[1<<8];
12 bool in[N][1<<8];
13 int S[N],P[N],st[N],fac[4],cf,cs;
14 queue<int> Q;
15 void addedge(int u,int v,int w){cur->v=v,cur->w=w,cur->nxt=Adj[u],Adj[u]=cur++;}
16 void up(int &a,int b){if(a==-1||a>b) a=b;}
17 void spfa(){
18     while(!Q.empty()){
19         int x=Q.front()/1000,y=Q.front()%1000;
20         Q.pop();
21         in[x][y]=0;
22         for(edge *i=Adj[x];i;i=i->nxt)
23             if(d[i->v][y|st[i->v]]==-1||d[x][y]+i->w<d[i->v][y|st[i->v]]){
24                 d[i->v][y|st[i->v]]=d[x][y]+i->w;
25                 if(y==(y|st[i->v])&&!in[i->v][y]) in[i->v][y]=1,Q.push(i->v*1000+y);
26             }                
27     }
28 }
29 bool check(int x){
30     int t=0;
31     for(int i=0;x;i++,x>>=1)
32         t+=(x&1)*(i<cf?fac[i]:-1);
33     return t>=0;
34 }
35 int cnt(int x){
36     int r=0;
37     for(int i=0;x;i++,x>>=1)
38         r+=(x&1)*(i<cf?0:1);
39     return r;
40 }
41 int main(){
42     while(scanf("%d",&n)+1){
43         cur=E;
44         cf=cs=0;
45         memset(Adj,0,sizeof(Adj));
46         memset(st,0,sizeof(st));
47         memset(d,-1,sizeof(d));
48         memset(dp,-1,sizeof(dp));        
49         int ans=0;
50         for(int i=1;i<=n;i++){            
51             scanf("%d%d",P+i,S+i);
52             if(S[i]&&P[i]) P[i]--,S[i]=0,ans++;
53             if(P[i]) st[i]=1<<cf,fac[cf++]=P[i],d[i][st[i]]=0;
54         }        
55         for(int i=1;i<=n;i++)
56             if(S[i])
57                 st[i]=1<<(cf+cs++),d[i][st[i]]=0;
58         nn=1<<(cf+cs);
59         
60         scanf("%d",&m);
61         while(m--){
62             int u,v,w;
63             scanf("%d%d%d",&u,&v,&w);
64             addedge(u,v,w);
65             addedge(v,u,w);
66         }
67         
68         for(int y=1;y<nn;y++){
69             for(int x=1;x<=n;x++){
70                 if(st[x]&&!(st[x]&y)) continue;
71                 for(int i=(y-1)&y;i;i=(i-1)&y)
72                     if(d[x][i|st[x]]!=-1&&d[x][(y-i)|st[x]]!=-1)
73                         up(d[x][y],d[x][i|st[x]]+d[x][(y-i)|st[x]]);
74                 if(d[x][y]!=-1) Q.push(x*1000+y),in[x][y]=1;
75             }
76             spfa();
77         }
78         for(int i=1;i<=n;i++)
79             for(int j=0;j<nn;j++)
80                 if(d[i][j]!=-1)
81                     up(dp[j],d[i][j]);
82         int num=0,cost=0;
83         for(int i=1;i<nn;i++)
84             if(check(i)){
85                 for(int j=(i-1)&i;j;j=(j-1)&i)
86                     if(check(j)&&check(i-j)&&dp[j]!=-1&&dp[i-j]!=-1)
87                         up(dp[i],dp[j]+dp[i-j]);
88                 int t=cnt(i);
89                 if(dp[i]!=-1&&(t>num||(t==num&&dp[i]<cost)))
90                     num=t,cost=dp[i];
91             }
92         printf("%d %d\n",num+ans,cost);
93     }
94 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小二的折腾日记

LeetCode-52-N-Queens-II

只返回N皇后问题结果的种数。 因此不需要每一个字符串置位了,只需要判断一个位置的横竖,斜45度和斜135度方向的值即可。依然采用递归的方式,这里需要注意的是,由...

6310
来自专栏C语言及其他语言

【每日一题】1426: [蓝桥杯][历届试题]九宫重排

如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面...

13130
来自专栏小红豆的数据分析

小蛇学python(18)pandas的数据聚合与分组计算

对数据集进行分组并对各组应用一个函数,这是数据分析工作的重要环节。在将数据集准备好之后,通常的任务就是计算分组统计或生成透视表。pandas提供了一个高效的gr...

30220
来自专栏王小雷

Python之数据规整化:清理、转换、合并、重塑

Python之数据规整化:清理、转换、合并、重塑 1. 合并数据集 pandas.merge可根据一个或者多个不同DataFrame中的行连接起来。 panda...

36560
来自专栏数据结构与算法

P1789 【Mc生存】插火把

题目背景 初一党应该都知道...... 题目描述 话说有一天linyorson在Mc开了一个超平坦世界,他把这个世界看成一个n*n的方阵,现在他有m个火把和k个...

37850
来自专栏章鱼的慢慢技术路

2013年第四届蓝桥杯C/C++B组省赛题目解析

24630
来自专栏欢乐玩转技术

Leetcode 137. 只出现一次的数字 II - 题解

https://leetcode.com/problems/single-number-ii/

92840
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (中)

上一部分提到了节点(Node),代价(Cost),估价公式等基本概念,有了这些知识铺垫 就可以正式开启寻路之旅了! ? 如上图,这是一个5行8列的网格,黄色节点...

27860
来自专栏ACM算法日常

交错字符串(动态规划)- leetcode 97

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

19310
来自专栏菩提树下的杨过

数据结构C#版笔记--啥夫曼树(Huffman Tree)与啥夫曼编码(Huffman Encoding)

哈夫曼树Huffman tree 又称最优完全二叉树,切入正题之前,先看几个定义 1、路径 Path 简单点讲,路径就是从一个指定节点走到另一个指定节点所经过的...

30190

扫码关注云+社区

领取腾讯云代金券