社区讨论

谁能帮我把这篇代码转成C语言?

学术版参与者 5已保存回复 10

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@mi7yn9h5
此快照首次捕获于
2025/11/21 05:45
4 个月前
此快照最后确认于
2025/11/21 05:45
4 个月前
查看原帖
CPP
#include<cstdio>
#include<cstring>
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline void swap(int &x,int &y){int t=x;x=y;y=t;}
inline int read()
{
	int s=0;bool f=false;
	char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=true;c=getchar();}
	while('0'<=c&&c<='9'){s=s*10+c-'0';c=getchar();}
	return f?-s:s;
}
int d[110000],fa[110000],son[110000],dep[110000],tot[110000],top[110000],ys[110000],yss[110000];
struct node
{
	int x,y,c,next;
}a[410000];int len,last[110000];
void ins(int x,int y,int c)
{
	len++;
	a[len].x=x;a[len].y=y;a[len].c=c;
	a[len].next=last[x];last[x]=len;
}
struct trnode
{
	int l,r,lc,rc,c;
}tr[410000];int trlen;
void bt(int l,int r)
{
	int now=++trlen;
	tr[now].l=l;tr[now].r=r;tr[now].c=0;
	tr[now].lc=tr[now].rc=-1;
	if(l<r)
	{
		int mid=(l+r)/2;
		tr[now].lc=trlen+1;bt(l,mid);
		tr[now].rc=trlen+1;bt(mid+1,r);
		tr[now].c=max(tr[tr[now].lc].c,tr[tr[now].rc].c);
	}
	else tr[now].c=d[yss[l]];
}
void change(int now,int x,int k)
{
	if(tr[now].l==tr[now].r){tr[now].c=k;return ;}
	int lc=tr[now].lc,rc=tr[now].rc;
	int mid=(tr[now].l+tr[now].r)/2;
	if(x<=mid)change(lc,x,k);
	else change(rc,x,k);
	tr[now].c=max(tr[lc].c,tr[rc].c);
}
int findmax(int now,int l,int r)
{
	if(tr[now].l==l&&tr[now].r==r)return tr[now].c;
	int lc=tr[now].lc,rc=tr[now].rc;
	int mid=(tr[now].l+tr[now].r)/2;
	if(r<=mid)return findmax(lc,l,r);
	else if(mid+1<=l)return findmax(rc,l,r);
	else return max(findmax(lc,l,mid),findmax(rc,mid+1,r));
}
int n,z;char p[10];
void dfs(int x)
{
	tot[x]=1;son[x]=0;
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa[x])
		{
			fa[y]=x;
			dep[y]=dep[x]+1;
			dfs(y);
			if(tot[son[x]]<tot[y])son[x]=y;
			tot[x]+=tot[y];
		}
	}
}
void dfs2(int x,int tp)
{
	ys[x]=++z;top[x]=tp;yss[z]=x;
	if(son[x]!=0)dfs2(son[x],tp);
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa[x]&&y!=son[x]){d[y]=a[k].c;dfs2(y,y);}
		else if(y==son[x])d[son[x]]=a[k].c;
	}
}
int solve(int x,int y)
{
	int tx=top[x],ty=top[y],ans=0;
	while(tx!=ty)
	{
		if(dep[tx]>dep[ty])
		{
			swap(x,y);swap(tx,ty);
		}
		ans=max(ans,findmax(1,ys[ty],ys[y]));
		y=fa[ty];ty=top[y];
	}
	if(x==y)return ans;
	else
	{
		if(dep[x]>dep[y])swap(x,y);
		return max(ans,findmax(1,ys[x]+1,ys[y]));
	}
}
int main()
{
	int T=read();
	while(T--)
	{
		len=0;memset(last,0,sizeof(last));
		
		memset(tr,0,sizeof(tr));
		
		memset(d,0,sizeof(d));
		memset(fa,0,sizeof(fa));
		memset(son,0,sizeof(son));
		memset(dep,0,sizeof(dep));
		memset(tot,0,sizeof(tot));
		memset(top,0,sizeof(top));
		memset(ys,0,sizeof(ys));
		memset(yss,0,sizeof(yss));
		n=read();
		for(int i=1,x,y,c;i<n;i++)
		{
			x=read();y=read();c=read();
			ins(x,y,c);ins(y,x,c);
		}
		fa[1]=0;dep[1]=1;dfs(1);
		z=0;dfs2(1,1);
		trlen=0;bt(1,z);
		while(1)
		{
			int x,y;scanf("%s",p);
			if(p[0]=='D')break;
			x=read();y=read();
			if(p[0]=='C')
			{
				int id=x*2,k=y;
				x=a[id].x;y=a[id].y;
				if(dep[x]>dep[y])change(1,ys[x],k);
				else change(1,ys[y],k);
			}
			else printf("%d\n",solve(x,y));
		}
	}
	return 0;
}

回复

10 条回复,欢迎继续交流。

正在加载回复...