SPOJ 375
2024-10-19 08:56:54
默默一看提交时间 ……
这是我以前的代码风格……
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define N 10005
#define lson(x) ((x<<1))
#define rson(x) ((x<<1)+1)
#define Del(a,b) memset(a,b,sizeof(a))
using namespace std;
int dep[N],siz[N],fa[N],id[N],son[N],val[N],top[N];
int num;
vector<int> v[N];
struct tree {
int x,y,val;
void read()
{
scanf("%d%d%d",&x,&y,&val);
}
}e[N];
void dfs1(int u, int f, int d)
{
dep[u] = d;
siz[u] = 1;
son[u] = 0;
fa[u] = f;
for (int i = 0; i < v[u].size(); i++)
{
int ff = v[u][i];
if (ff == f) continue;
dfs1(ff, u, d + 1);
siz[u] += siz[ff];
if (siz[son[u]] < siz[ff])
son[u] = ff;
}
}
void dfs2(int u, int tp) {
top[u] = tp;
id[u] = ++num;
if (son[u]) dfs2(son[u], tp);
for (int i = 0; i < v[u].size(); i++) {
int ff = v[u][i];
if (ff == fa[u] || ff == son[u]) continue;
dfs2(ff, ff);
}
}
struct Tree
{
int l,r,val;
};
Tree tree[4*N];
void pushup(int x)
{
tree[x].val = max(tree[lson(x)].val, tree[rson(x)].val);
}
void build(int l,int r,int v)
{
tree[v].l=l;
tree[v].r=r;
if(l==r)
{
tree[v].val=val[l];
return ;
}
int mid=(l+r)>>1;
build(l,mid,v*2);
build(mid+1,r,v*2+1);
pushup(v);
}
void update(int o,int v,int val)
{
if(tree[o].l==tree[o].r)
{
tree[o].val = val;
return ;
}
int mid = (tree[o].l+tree[o].r)/2;
if(v<=mid)
update(o*2,v,val);
else
update(o*2+1,v,val);
pushup(o);
}
int query(int x,int l, int r)
{
if (tree[x].l >= l && tree[x].r <= r)
{
return tree[x].val;
}
int mid = (tree[x].l + tree[x].r) / 2;
int ans = 0;
if (l <= mid) ans = max(ans, query(lson(x),l,r));
if (r > mid) ans = max(ans, query(rson(x),l,r));
return ans;
}
int Yougth(int u, int v)
{
int tp1=top[u],tp2=top[v];
int ans=0;
while (tp1!=tp2)
{
if (dep[tp1] < dep[tp2])
{
swap(tp1, tp2);
swap(u,v);
}
ans=max(query(1,id[tp1],id[u]),ans);
u=fa[tp1];
tp1=top[u];
}
if(u==v)return ans;
if(dep[u]>dep[v])swap(u, v);
ans=max(query(1,id[son[u]],id[v]),ans);
return ans;
}
void Clear(int n)
{
for(int i=1;i<=n;i++)
v[i].clear();
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
e[i].read();
v[e[i].x].push_back(e[i].y);
v[e[i].y].push_back(e[i].x);
}
num = 0;
dfs1(1,0,1);
dfs2(1,1);
for (int i = 1; i < n; i++)
{
if (dep[e[i].x] < dep[e[i].y]) swap(e[i].x, e[i].y);
val[id[e[i].x]]=e[i].val;
}
build(1,num,1);//构造线段树
char s[200];
while(~scanf("%s",&s)&&s[0]!='D')
{
int x,y;
scanf("%d%d",&x,&y);
if(s[0]=='Q')
printf("%d\n",Yougth(x,y));
if (s[0] == 'C')
update(1,id[e[x].x],y);
}
Clear(n);
}
return 0;
}
好像不太对
#include <algorihtm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#define N 100005
using namespace std;
void read(int &s){
char ch=getchar();int f=1;
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(s=0;isdigit(ch);s=s*10+ch-'0',ch=getchar());
s*=f;
}
int son[N],val[N],top[N];
int dep[N],siz[N];
int fa[N],id[N];
int num;
struct Edge{
int u,v,nxt,val;
}e[N];
void AddEdge(int u,int v,int value){
e[++tot].v=v;e[tot].nxt=head[u];
head[u]=tot;e[tot].val=value;e[tot].u=u;
e[++tot].v=u;e[tot].nxt=head[v];
head[v]=tot;e[tot].val=value;e[tot].u=v;
}
void dfs1(int u,int f){
dep[u]=dep[f]+1;int to;
siz[u]=1;son[u]=0;fa[u]=f;
for(int i=head[u];i;i=e[i],nxt){
to=e[i].v;
if(f=to)continue;
dfs1(to,u);size[u]+=siz[to];
if(siz[son[u]]<siz[to])son[u]=to;
}
}
void dfs2(int u,int to){
top[u]=to;id[u]=++num;int v;
if(son[u])dfs(son[u],to);
for(int i=head[u];i;i=e[i].nxt){
int v=e[u].v;
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
struct T{
int l,r,val;
}t[N<<2];
void pushup(int x){
t[x].val=max(t[x<<1].val,t[x<<1|1].val);
}
void build(int l,int r,int ret){
t[ret].l=l;t[ret].r=r;
if(l==r){
t[ret].val=val[l];
return ;
}
int mid=(l+r)>>1;
build(l,mid,ret<<1);
build(mid+1,r,ret<<1|1);
pushup(ret);
}
void update(int ret,int pos,int val){
if(t[ret].l==t[ret].r){
t[ret].val=val;
return;
}
int mid=(t[ret].l+t[ret].r)>>1;
if(pos<=mid)update(ret<<1,pos,val);
else update(ret<<1|1,pos,val);
pushup(ret);
}
int query(int L,int R,int ret){
if(t[ret].l>=l&&t[ret].r<=r)
return t[ret].val;
int mid=(t[ret].l+t[ret].r)>>1;
int ans=0;
if(L<=mid)ans=max(ans,query(ret<<1,L,R));
if(R>mid)ans=max(ans,query(ret<<1|1,L,R));
return ans;
}
int Youth(int u,int v){
int t1=top[u],t2=top[v];
int ans=0;
while(t1!=t2){
if(dep[t1]<dep[t2]){
swap(t1,t2);
swap(u,v);
}
ans=max(query(id[t1],id[u],1),ans);
u=fa[t1];
t1=top[u];
}
if(u==v)return ans;
if(dep[u]>dep[v])swap(u,v);
ans=max(query(id[son[u]],id[v],1),ans);
return ans;
}
void Clear(int n){
for(int i=1;i<=n;++i)
head[i]=0;
tot=0;
}
int main(){
int T,a,b,c,;read(T);
while(T--){
int n;read(n);
for(int i=1;i<n;++i){
read(a),read(b),read(c);
AddEdge(a,b,c);
}
num=0;
dfs1(1,0,1);
dfs2(1,1);
for(int i=1;i/2<n;++i){
if(dep[e[i].u]<dep[e[i].y])swap(e[i].x,e[i].y);
val[id[e[i].u]]=e[i].val;
}
build(1,num,1);
char s[200];
while(~scanf("%s",&s)&&s[0]!='D'){
int x,y;
scanf("%d%d",&x,&y);
if(s[0]=='Q')
printf("%d\n",Youth(x,y));
if(s[0]=='C')
update(1,id[e[x].u],y);
}
Clear(n);
}
return 0;
最新文章
- js的this和面向对象编程
- js 基础
- mvc中测试网络
- 转载_虚拟机下LInux(终端)配置网络的方法
- 消息队列通信,王明学learn
- 循环调用MAIN
- 深度学习笔记（三 ）Constitutional Neural Networks
- 万能js实现翻页，动态生成内容自动翻页，兼容各种浏览器（已测试）----神器版！
- POJ C程序设计进阶 编程题＃1：含k个3的数
- 做优步有什么旁门左道吗？No，贪小便宜会吃大亏！
- 算法之旅，直奔<algorithm>之十五 find
- Struts2 stracture
- [原创]一种基于Python爬虫和Lucene检索的垂直搜索引擎的实现方法介绍
- Java 9 揭秘（19. 平台和JVM日志）
- Java基础-方法(07)
- 第1次作业：no blog no fun
- 一览Django框架（转载）
- jQuery的选择器中的通配符[id^='code']或[name^='code']及jquery选择器总结
- RabbitMQ 选型和对比
- 微信小程序—获取用户网络状态和设备的信息