题解们： T1:https://blog.csdn.net/xuxiayang/article/details/102825559 T2:https://blog.csdn.net/xuxiayang/article/details/102864865 T3:https://blog.csdn.net/xuxiayang/article/details/102867993
人均T1谢谢。。。
T2暴力开
O
2
O_2
O2就80了，打正解的wyc大爷哭晕在厕所。。。
一些暴力代码
T2
C
o
d
e
Code
Code(80分)
#pragma GCC optimize(2)
%:pragma GCC
optimize(3)
%:pragma GCC
optimzie("Ofast")
%:pragma GCC
optimize("inline")
#include<cctype>
#include<cstdio>
#define LL long long
#define N 100010
#define mod 1000000007
using namespace std
;int n
,l
[N
],k
,tot
,vis
[N
],dis
[N
];
struct node
{int next
,to
;}e
[N
<<1];
inline void add(int u
,int v
){e
[++tot
]=(node
){l
[u
],v
};l
[u
]=tot
;return;}
LL ans
[N
];
inline LL
read()
{
char c
;LL d
=1,f
=0;
while(c
=getchar(),!isdigit(c
)) if(c
=='-') d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
inline void dfs(int x
,int fa
,int dep
)
{
if(dep
>k
) return;
dis
[x
]=1;
for(register int i
=l
[x
];i
;i
=e
[i
].next
)
{
int y
=e
[i
].to
;
if(y
==fa
) continue;
dfs(y
,x
,dep
+1);
if(dep
<k
) vis
[++vis
[0]]=y
,dis
[x
]+=dis
[y
];
}
return;
}
signed main()
{
n
=read();k
=read();
for(register int i
=1,x
,y
;i
<n
;i
++)
{
x
=read();y
=read();
add(x
,y
),add(y
,x
);
}
for(register int i
=1;i
<=n
;i
++)
{
vis
[0]=0;dis
[i
]=1;
dfs(i
,0,0);
printf("%d ",vis
[0]+1);
if(vis
[0]) ans
[i
]=dis
[i
];
for(register int j
=1;j
<=vis
[0];j
++) ans
[i
]=ans
[i
]*dis
[vis
[j
]]%mod
;
}
putchar(10);
for(register int i
=1;i
<=n
;i
++) printf("%lld ",ans
[i
]);
}
T3
C
o
d
e
Code
Code(40分)
#include<cstdio>
#include<cstring>
#define N 200051
#define M 1052551
using namespace std
;int n
,q
,x
,y
;
struct node
{int next
,to
;}edge
[M
];int l
[M
],tot
,maxn
,link
[N
];
bool vis
[N
],t
[N
];
inline void add(int u
,int v
){edge
[++tot
].to
=v
;edge
[tot
].next
=l
[u
];l
[u
]=tot
;return;}
bool ok
,spe
=1;
inline int read()
{
char c
;int f
=0,d
=1;
while((c
=getchar())<48||c
>57)if(c
=='-')d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while((c
=getchar())>=48&&c
<=57)f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
inline bool find(int p
)
{
for(int i
=l
[p
];i
;i
=edge
[i
].next
)
{
int v
=edge
[i
].to
;
if(!vis
[v
])
{
vis
[edge
[i
].to
]=1;
if(!link
[v
]||find(link
[v
]))
{
link
[v
]=p
;
return true;
}
}
}
return false;
}
signed main()
{
maxn
=read();n
=read();
for(register int i
=1;i
<=n
;i
++) x
=read(),y
=read(),add(x
,i
),add(y
,i
),spe
&=x
==y
,t
[x
]++;
if(spe
)
{
int s
[N
]={0};
for(register int i
=1;i
<=maxn
;i
++) s
[i
]=s
[i
-1]+t
[i
];
q
=read();
while(q
--)
{
x
=read();y
=read();
puts(s
[y
]-s
[x
-1]==(y
-x
+1)?"Yes":"No");
}
return 0;
}
q
=read();
while(q
--)
{
x
=read();y
=read();ok
=true;
memset(link
,0,sizeof(link
));
for(register int i
=x
;i
<=y
;i
++)
{
memset(vis
,0,sizeof(vis
));
if(!find(i
)) {ok
=false;break;}
}
puts(ok
?"Yes":"No");
}
}
