### T1

```#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 600010

int n,m;
struct edge{int y,next;}e[maxn<<1];
int first[maxn],len=0;
int f[maxn][20],g[maxn],deep[maxn];
void dfs(int x,int fa,int dep)
{
f[x][0]=fa;deep[x]=dep;
for(int i=first[x];i;i=e[i].next)
if(e[i].y!=fa)dfs(e[i].y,x,dep+1);
}
int get_lca(int x,int y)
{
if(deep[x]>deep[y])swap(x,y);
for(int i=19;i>=0;i--)if(deep[f[y][i]]>=deep[x])y=f[y][i];
if(x!=y){for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];x=f[x][0];}
return x;
}
long long ans=0;
void get_ans(int x,int fa)
{
for(int i=first[x];i;i=e[i].next)
if(e[i].y!=fa)get_ans(e[i].y,x),g[x]+=g[e[i].y];
if(g[x]==1&&x!=1)ans++;//只能删子树里延伸出去的那条
if(g[x]==0&&x!=1)ans+=m;//随便删一条黑线
}

int main()
{
scanf("%d %d",&n,&m);
for(int i=1,x,y;i<n;i++)scanf("%d %d",&x,&y),
for(int j=1;j<=19;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];
for(int i=1,x,y;i<=m;i++)
{
scanf("%d %d",&x,&y);
int lca=get_lca(x,y);
g[x]++,g[y]++;g[lca]-=2;
}
get_ans(1,0);printf("%lld",ans);
}```

### T2

，发现这是个等比数列的形式，所以有

\$\$

```#include <cstdio>
#define maxn 2000010
#define mod 998244353

int n,a,b,f[maxn];

int main()
{
scanf("%d %d %d",&n,&a,&b);
f[1]=1,f[2]=a+1;for(int i=3;i<=n;i++)f[i]=(1ll*(a+1)*f[i-1]%mod+1ll*b*f[i-2]%mod)%mod;
printf("%d",f[n]);
}```

### T3

```#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 310
#define MS(f) memset(f,0,sizeof(f))
#define ll long long

int n;
struct point{
ll x,y;int id;point(ll xx=0,ll yy=0,int Id=0):x(xx),y(yy),id(Id){};
point operator +(const point &B)const{return point(x+B.x,y+B.y);}
point operator -(const point &B)const{return point(x-B.x,y-B.y);}
ll operator ^(const point &B)const{return x*B.y-y*B.x;}
bool operator ==(const point &B)const{return x==B.x&&y==B.y;}
}a[maxn],s,t;vector<point> b[maxn];
ll ans=0,S1[maxn],S2[maxn],T1[maxn],T2[maxn];
point c[maxn],d[maxn];int t1,t2;
void solve(int x,int y)
{
MS(S1);MS(S2);MS(T1);MS(T2);t1=t2=0;
for(int i=0;i<n-1;i++)if(b[x][i]==t)
for(int j=(i+1)%(n-1);j!=i;j=(j+1)%(n-1))
if(((b[x][j]-s)^(t-s))>0)c[++t1]=b[x][j];else d[++t2]=b[x][j];
//右边的点放在c里，左边的放在d里
ans+=t1*(t1-1)*(t1-2)/6+t2*(t2-1)*(t2-2)/6;//左右的方案数
int j=t2;for(int i=t1;i>=1;i--)//st下面的方案数
{
while(j>=1&&((s-c[i])^(d[j]-c[i]))<0)S2[d[j].id]=t1-i,j--;
S1[c[i].id]=j; ans+=(t1-i)*j+j*(j-1)/2;
//S1记录c[i]能够和多少个d[j]构成一条在s下方的线段，S2记录d[j]
//ans得到的贡献是选c[i]，再选两个点的方案数
}
while(j>=1)S2[d[j].id]=t1,j--; t1=t2=0;

for(int i=0;i<n-1;i++)if(b[y][i]==s)
for(int j=(i+1)%(n-1);j!=i;j=(j+1)%(n-1))
if(((b[y][j]-s)^(t-s))>0)c[++t1]=b[y][j];else d[++t2]=b[y][j];
j=1;for(int i=1;i<=t1;i++)
{
while(j<=t2&&((t-c[i])^(d[j]-c[i]))>0)T2[d[j].id]=i-1,j++;
T1[c[i].id]=t2-j+1; ans+=(t2-j+1)*(i-1)+(t2-j+1)*(t2-j)/2;
}
while(j<=t2)T2[d[j].id]=t1,j++;
for(int i=1;i<=n;i++)ans+=S1[i]*T1[i]+S2[i]*T2[i];//包含该线段的三角形数
}
bool cmp(point x,point y){
ll xx=(x-s)^(t-s),yy=(y-s)^(t-s);
if(xx*yy>0)return ((x-s)^(y-s))<0;return xx>0;
}

int main()
{
scanf("%d",&n);if(n<5)return printf("0"),0;
for(int i=1;i<=n;i++)scanf("%lld %lld",&a[i].x,&a[i].y),a[i].id=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)if(i!=j)b[i].push_back(a[j]);
s=a[i];t=b[i][0];sort(b[i].begin()+1,b[i].end(),cmp);//顺时针排序
}
for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)s=a[i],t=a[j],solve(i,j);
printf("%lld\n",ans);
}```